基于比较的排序算法有哪些

基于比较的排序算法有哪些

七种排序算法[1]分别是：

•

四种基本排序算法：冒泡排序，选择排序，插入排序，希尔排序。

•

三种高级排序算法：归并排序，快速排序，堆排序。

这七种排序算法都是比较排序算法，这种算法的特点顾名思义就是排序是依赖于元素间两两比较的结果[2]。

任何比较算法在最坏的情况下都要经过Ω(nlgn)次比较。

1. 冒泡排序

顾名思义，冒泡排序的整个过程就像碳酸饮料 中的小气泡，慢慢浮到最上面。只不过在冒泡排序中浮上去的是最大的数而已。

简要思路： 遍历数组，每次比较相邻的两个元素 arr[i],

arr[i + 1]，如果 arr[i + 1] < arr[i] ，就把 arr[i + 1]

和 arr[i] 调换位置。

冒泡排序有这样的排序特性：

•

每次都只排好一个元素。

•

最坏情况时间复杂度为O(n^2)。

•

平均情况时间复杂度为O(n^2)。

•

需要额外空间O(1)。

•

所需时间与输入数组的初始状态无关。

算法示例

public static void bubbleSort(int[] arr) {

int n = ;

// 每一次循环，都把最大的元素冒泡到对应的位置

for (int i = 0; i < n - 1; ++i) {

for (int j = 0; j < n - i - 1; ++j) {

// 如果后一个比前一个小，那么就把大的放后面

if (less(arr, j + 1, j)) exch(arr, j, j +

1);

}

}

}

2. 选择排序

其实选择排序，直观上来说和冒泡排序差不多，只不过么有了相邻元素频繁交换的操作，但是却保留了冒泡排序频繁访问数组的特点。

简要思路:对于每一个循环，我们在剩余的未排序数中找到最小数对应的下标，遍历一次后再把对应的数放到合适的位置。

选择排序有这样的排序特性：

•

每次循环都只排好一个元素。

•

最坏情况时间复杂度为Theta (n^2)。

•

平均情况时间复杂度为Theta (n^2)。

•

需要额外空间为O(1)。

•

所需时间和输入数组的初始状态无关。

算法示例

public static void selectionSort(int[] arr) {

int n = ;

// 每一次循环，都会把剩余未排数组的最小值放到对应的位置上去

for (int i = 0; i < n; ++i) {

int min = i;

for (int j = i + 1; j < n; ++j) {

if (less(arr, j, min)) min = j;

}

exch(arr, min, i);

}

}

3. 插入排序

插入排序和前面两个基本排序算法有相似性质，多了的一条就是对输入的数组的随机性有了一定关系，加入输入数组已经基本有序，时间复杂度会降为O(n)。

简单思路:类似于打牌的时候整理自己手里的扑克牌。一次选择一张卡，并将其插入先前订购的卡的正确位置。

插入排序有这样的排序特性：

•

每次排好一个元素。

•

最坏情况时间复杂度为Theta (n^2)。

•

平均情况时间复杂度为Theta (n^2)。

•

需要额外空间为O(1)。

•

所需时间与输入数组的初始状态有关。

算法示例

public static void insertSort(int[] arr) {

int n = ;

for (int i = 1; i < n; ++i) {

// [0, i - 1] 已经有序了，然后把 arr[i] 插入到

[0, i - 1] 中合适位置就好了

// 放好之后，就可以停止遍历了，因为前面的也一定是排好序的

for (int j = i; j > 0 && less(arr, j, j - 1);

--j) {

exch(arr, j, j - 1);

}

}

}

4. 希尔排序

Hill排序本质上是插入排序的改进版本，其性能依赖于主观参数的调整。到目前为止，彻底分析Hill排序的排序性能仍然具有挑战性(不完整)，所以这里主要分析算法的特点。

简要思路： 在插入排序中，每一次只移动了一个元素嘛，所以在希尔排序中，为了加快排序速度改进了交换步长。通过交换不相邻的元素对数组进行局部排序，并在小的分组中使用插入排序来完成。

希尔排序的排序特性：

•

性能依赖于参数 h （步长）的设置，而 h 的设置又依赖于 h 序列的性质 ……

算法示例

public static void shellSort(int[] arr) {

int n = ;

int h = 1; // 这就是传说中的那个步长

while (h < n / 3) h = 3 * h + 1; // 1, 4, 13, 40...

while (h >= 1) {

for (int i = h; i < n; ++i) {

// 插入排序，从原来的 [j, j - 1] 变成了 [j,

j - h]

for (int j = i; j >= h && less(arr, j, j -

h); j -= h) exch(arr, j, j - h);

}

h /= 3;

}

}

5. 归并排序

有意思的来了， 归并排序顾名思义依赖于归并这个操作，详细来说就是将两个有序数组进行归并。

简要思路： 将一个大数组排序，可以先将其切分成两个小数组分别排序，对于两个小数组，又可以分别将两个小数组切分成两个小小数组进行排序……各自完成排序后，向上归并，那么整体就有序了。

归并排序算法特性：

•

任意长的数组n，排序时间和nlgn成正比。

•

最坏情况时间复杂度Theta (nlgn)。

•

平均情况时间复杂度Theta (nlgn)。

•

需要额外空间为O(n)。

•

小规模应使用插入排序，避免过度调用递归。

算法示例

public static void mergeSort(int[] arr) {

mergeSort(arr, 0, - 1, new

int[]);

}

private static void mergeSort(int[] arr, int left, int

right, int[] aux) {

if (left >= right) return;

// 找到切分中点位置

int mid = left + (right - left) / 2;

mergeSort(arr, left, mid, aux); // 排序左边

mergeSort(arr, mid + 1, right, aux); // 排序右边

merge(arr, left, mid, right, aux); // 归并最后的结果

}

// 归并函数

private static void merge(int[] arr, int left, int mid,

int right, int[] aux) {

for (int k = left; k <= right; ++k) aux[k] =

arr[k];

int i = left, j = mid + 1;

for (int k = left; k <= right; ++k) {

if (i > mid) arr[k] = aux[j++]; // 如果左半部分已经放完了，那么就只放右边的

else if (j > right) arr[k] = aux[i++]; // 同样的，如果右半部分已经都放进去了，就只放左边的

else if (less(aux, i, j)) arr[k] = aux[i++];

// 否则的话，捡着小的放

else arr[k] = aux[j++];

}

}

6. 快速排序

更有意思的来了！ 快速排序是目前应用最广，最有意思的一个排序算法，速度快，空间利用率高，名副其实是理想中最快的算法了。

简要思路： 快速排序和归并排序正好互补，归并排序是将两个有序子数组进行归并后，整个子数组就有序了，而快速排序是当两个子数组都有序的时候，整个数组也就有序了。

与归并排序的不同：

•

归并排序的递归发生在处理整个数组前，快速排序的递归发生在处理整个数组后。

•

归并排序是将数组切分为两个长度一致（或差一个）的子数组，快速排序的切分结果依赖于 partition 函数的结果，也就是依赖于数组的内容。

快速排序算法特性：

•

时间复杂度和空间复杂度都很优秀，就像是上一节课的学霸。学好体育也不错。

•

最坏情况时间复杂度为Theta (n^2)。

•

平均情况时间复杂度为Theta (nlgn)。

•

空间复杂度O(1)。

•

只有当原始数组完全随机化才会达到理论上最优情况，那么相反的，如果数组原来就有序，这时候就成了快速排序的最差情况。

•

对于小数组，最好插入sort。

public static void quickSort(int[] arr) {

quickSort(arr, 0, - 1);

}

private static void quickSort(int[] arr, int left, int

right) {

if (left > right) return;

int mid = partition(arr, left, right);

quickSort(arr, left, mid - 1);

quickSort(arr, mid + 1, right);

}

private static int partition(int[] arr, int left, int

right) {

int val = arr[left];

int lo = left, hi = right + 1;

while (true) {

while (arr[++lo] <= val) if (lo >= right)

break;

while (arr[--hi] >= val) if (hi <= left) break;

if (lo >= hi) break;

exch(arr, lo, hi);

}

exch(arr, left, hi);

return hi;

}

7. 堆排序

最有意思的来了！堆排序其实是一个意外收获，因为一开始就是利用堆的数据结构。后来大家伙发现可以用来排序，就有了现在的堆排序。

简要思路： 在堆的构建阶段，将数据从数组中逐个放到堆中。在排序结果的获取阶段，将数据再从堆中挨个放到数组中。

堆排序算法特性：

•

取决于堆的基本特征，例如浮动和下沉操作。

•

最坏情况时间复杂度为O(nlgn)。

•

现代设备中很少使用它，因为元素很少和相邻的其他元素作比较，因此缓存未命中的次数要远远高于其他对相邻元素作比较的算法。

•

经常使用堆实现的优先级队列。

public static void heapSort(int[] arr) {

int n = ;

int[] heap = new int[n + 1];

int idx = 0;

// 将元素挨个入堆，并上浮

for (int num : arr) {

heap[++idx] = num;

swim(heap, idx);

}

// 构建排序结果

for (int i = 0; i < n; ++i) arr[i] =

deleteMin(heap, idx--);

}

// 删除堆中的最小元素，并重新调整堆

private static int deleteMin(int[] arr, int idx) {

int ret = arr[1];

exch(arr, 1, idx--);

arr[idx + 1] = 0;

sink(arr, 1, idx);

return ret;

}

// 堆的下沉操作

private static void sink(int[] arr, int k, int idx) {

while (2 * k <= idx) {

int j = 2 * k;

if (j < idx && less(arr, j + 1, j)) ++j;

if (!less(arr, j, k)) break;

exch(arr, j, k);

k = j;

}

}

// 堆的上浮操作

private static void swim(int[] arr, int idx) {

while (idx > 1 && less(arr, idx, idx / 2)) {

exch(arr, idx, idx / 2);

idx /= 2;

}

}

对于前面四种基本算法，优化的空间就不是很大了，但是对于后面的三种基本算法plus，还是有很多优化的空间的，不过呢，整体思路都是一样的。

洗洗睡洗洗睡了 ，(⊙o⊙)，差点忘了继续记录，这周力扣爬到了1,322。

参考资料

[1]

《算法》第四版:

第二章：排序

[2]

《算法导论》第三版:

第二部分：排序和顺序统计量