冒泡排序算法
冒泡排序（英语：Bubble Sort）是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序（如从大到小、首字母从A到Z）错误就把他们交换过来
//单向冒泡排序算法
private static void bubbleSort(int[] arr) {
int tmp;
boolean ok;
for (int i = 0; i < arr.length / 2 + 1; i++) {
ok = false;
for (int j = 0; j < arr.length - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
ok = true;
tmp = arr[j + 1];
arr[j + 1] = arr[j];
arr[j] = tmp;
}
}
if (!ok) break;
}
}
//双向冒泡排序算法
private static void doubleBubbleSort(int[] arr) {
int tmp;
boolean ok;
for (int i = 0; i < arr.length / 2 + 1; i++) {
ok = false;
for (int j = 0; j < arr.length - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
ok = true;
tmp = arr[j + 1];
arr[j + 1] = arr[j];
arr[j] = tmp;
}
}
if (!ok) break;
ok = false;
for (int j = arr.length - i - 2; j > i; j--) {
if (arr[j - 1] > arr[j]) {
ok = true;
tmp = arr[j - 1];
arr[j - 1] = arr[j];
arr[j] = tmp;
}
}
if (!ok) break;
}
}
选择排序算法
选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理如下。首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
private static void selectionSort(int[] arr) {
int min,min_index;
for (int i = 0; i < arr.length; i++) {
min = arr[i];
min_index = i;
for (int j = i; j < arr.length; j++) {
if (min > arr[j]){
min = arr[j];
min_index = j;
}
}
arr[min_index] = arr[i];
arr[i] = min;
}
}
插入排序
插入排序（英语：Insertion Sort）是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到 {\displaystyle O(1)} {\displaystyle O(1)}的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。
public static void insertSort(int arr[]) {
int i, j, temp;
for (i = 1; i < arr.length; i++) {
temp = arr[i];
for (j = i; j > 0 && arr[j - 1] > temp; j--)
arr[j] = arr[j - 1];
arr[j] = temp;
}
}
python版
# 简单插入排序
def binary_sort(arr):
for i in range(1, len(arr)):
tmp = arr[i]
j = i
while j > 0 and tmp < arr[j - 1]:
arr[j] = arr[j - 1]
j -= 1
arr[j] = tmp
# 二分法插入排序
def binary_sort(arr):
for i in range(1, len(arr)):
tmp = arr[i]
j = i
left = 0
right = i - 1
while left <= right:
mid = (left + right) // 2
if arr[mid] > tmp:
right = mid - 1
else:
left = mid + 1
while j > left:
arr[j] = arr[j - 1]
j -= 1
arr[j] = tmp
希尔排序
希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。希尔排序是非稳定排序算法。
- 希尔排序是基于插入排序的以下两点性质而提出改进方法的：
- 插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率
但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位
快速排序
python代码实现
def quick_sort(arr, left, right):
if left < right:
start = arr[left]
i, j = left, right
while i < j:
while arr[j] > start and j > i: j -= 1
if j > i:
arr[i] = arr[j]
i += 1
else:
break
while arr[i] < start and j > i: i += 1
if j > i:
arr[j] = arr[i]
j -= 1
else:
break
arr[i] = start
quick_sort(arr, left, i - 1)
quick_sort(arr, i + 1, right)
基数排序
def radix_sort(arr, maxDigit):
mod = 10
dev = 10
counter = [[] for _ in range(mod)]
for i in range(maxDigit):
for j in range(len(arr)):
if arr[j] >= dev ** i:
bucket = arr[j] // (dev ** i) % mod
counter[bucket].append(arr[j])
if i > 0:
old_bucket = arr[j] // (dev ** (i - 1)) % mod
counter[old_bucket].remove(arr[j])
elif counter[0].count(arr[j]) == 0:
counter[0].append(arr[j])
counter[int(str(arr[j])[0])].remove(arr[j])
arr.clear()
for iters in counter:
for iter in iters:
arr.append(iter)
归并排序
def merge_sort(arr01, arr02):
i, j = 0, 0
arr = []
l01, l02 = len(arr01), len(arr02)
for _ in range(l01 + l02):
if j != l02 and (i == l01 or arr01[i] > arr02[j]):
arr.append(arr02[j])
j += 1
else:
arr.append(arr01[i])
i += 1
return arr
网友评论