经典八大排序算法

编程入门行业动态更新时间:2024-10-07 20:28:19

经典八大排序<a href=https://www.elefans.com/category/jswz/34/1770096.html style= 算法"/>

经典八大排序算法

排序的稳定性

数组arr中有若干元素，其中A元素和B元素相等，并且A元素在B元素前面，如果使用某种排序算法排序后，能够保证A元素依然在B元素的前面，可以说这个该算法是稳定的。
稳定性的意义：
如果一组数据只需要一次排序，则稳定性一般是没有意义的，如果一组数据需要多次排序，稳定性是有意义的。例如要排序的内容是一组商品对象，第一次排序按照价格由低到高排序，第二次排序按照销量由高到低排序，如果第二次排序使用稳定性算法，就可以使得相同销量的对象依旧保持着价格高低的顺序展现，只有销量不同的对象才需要重新排序。这样既可以保持第一次排序的原有意义，而且可以减少系统开销。
稳定性口诀： 考研很辛苦，心情不稳定。快（快排）些（希尔）选（选择）一堆（堆排）朋友去干饭（干啥都行）。

一、冒泡排序

比较相邻的两个元素。如果前一个元素比后一个元素大，就交换这两个元素的位置。所以第一次排序比较完，最大的数在数组的最后一个位置上。依此类推。

class Bubble {public static int[] method(int a[]) {for (int i = 0; i < a.length - 1; i++) {for (int j = 0; j < a.length - 1 - i; j++) {if (a[j] > a[j + 1]) {int temp = a[j];a[j] = a[j + 1];a[j + 1] = temp;//这里可以用异或进行交换，也可以使用求和}}}return a;}//测试public static void main(String[] args) {int[] a = {11, 45, 22, 18, 6};int[] m = method(a);for (int i : m) {System.out.println(i);}}
}

优化之flag标记

class Bubble {public static void bubbleSort(int[] a){//外层循环是排序的趟数//内层循环控制每一趟比较的次数，每一趟比完一次，就少了一次排序，所以内层循环次数要减去i//这个flag是为了如果数组的元素刚好是有序的，就不用比较，直接returnfor(int i = 0; i < a.length - 1; i++){boolean flag = true;for(int j = 0; j < a.length - 1 - i; j++){if(a[j] > a[j + 1]){int temp = a[j];a[j] = a[j + 1];a[j + 1] = temp;flag = false;}}if(flag)  return;}}
}

优化之双指针

    public static void bubble(int[] a) {int i = 0, j = a.length - 1;while (i <= j) {for (int p = i; p <= j; p++) {if (a[p] > a[j]) {int tmp = a[p];a[p] = a[j];a[j] = tmp;}if (a[p] < a[i]) {int tmp = a[p];a[p] = a[i];a[i] = tmp;}}i++;j--;}}

平均时间复杂度：O(n ^ 2) 最好情况：O(n) 空间复杂度：O(1) 稳定性：稳定

冒泡排序就是把小的元素往前调或者把大的元素往后调。比较是相邻的两个元素比较，交换也发生在这两个元素之间。所以，如果两个元素相等，我想你是不会再无聊地把他们俩交换一下的；如果两个相等的元素没有相邻，那么即使通过前面的两两交换把两个相邻起来，这时候也不会交换，所以相同元素的前后顺序并没有改变，所以冒泡排序是一种稳定排序算法。

二、选择排序

每一次遍历的过程中，都假定第一个索引处的元素是最小值，和其他索引处的值依次进行比较，如果当前索引处的值大于其他某个索引处的值，则假定其他某个索引处的值为最小值，最后可以找到最小值所在的索引。

class SelectionSort{public static void selectionSort(int[] a){//外层循环是排序的趟数for(int i = 0; i < a.length - 1; i++){int k = i;//内层循环就是为了找到最小值所在的索引 kfor(int j = k + 1; j < a.length; j++){if(a[j] < a[k]){ //那第一个数和后面的数比较，找到它并记录它的索引值k = j;}}//如果 i 不是最小的值的那个索引，就交换。反之不交换if(i != k){int temp = a[i];a[i] = a[k];a[k] = temp;}}}
}

平均时间复杂度：O(n ^ 2) 最好情况：O(n^2) 空间复杂度：O(1) 稳定性：不稳定

两个相等的元素可能会交换位置，比如5，5，1，2；所以选择排序是不稳定的

三、插入排序

将一个记录插入到已排好序的序列中，从而得到一个新的有序序列

class InsertSort{public static void insertSort(int[] a){int temp;//外层循环是排序的趟数,从1开始是因为将第0位看成有序数据for(int i = 1; i < a.length; i++){if(a[i] < a[i - 1]){//待插入小于有序序列最后一个元素，向前插入temp = a[i];//保存待插入的数for(int j = i; j >= 0; j--){//倒叙遍历有序序列//j>0是因为如果会比较到最后一个数，此时j=0if(j > 0 && a[j - 1] > temp){//肯定是从i的前一个元素比较a[j] = a[j - 1]; }else{a[j] = temp; break;}}}}}
}

平均时间复杂度：O(n ^ 2) 最好情况：O(n) 空间复杂度：O(1) 稳定性：稳定

插入排序是在一个已经有序的小序列的基础上，一次插入一个元素。当然，刚开始这个有序的小序列只有1个元素，就是第一个元素。比较是从有序序列的末尾开始，也就是想要插入的元素和已经有序的最大者开始比起，如果比它大则直接插入在其后面，否则一直往前找直到找到它该插入的位置。如果碰见一个和插入元素相等的，那么插入元素把想插入的元素放在相等元素的后面。所以，相等元素的前后顺序没有改变，从原无序序列出去的顺序就是排好序后的顺序，所以插入排序是稳定的。比如2，4，8，4

四、希尔排序

希尔排序是插入排序的一种，又称“缩小增量排序”，是插入排序算法的一种更高效的改进版本。

选定一个增长量h（数组长度的一半），按照增长量h作为数据分组的依据，对数据进行分组；

对分好组的每一组数据完成插入排序；减小增长量，最小减为1，重复第二步操作。

class ShellSort{public static void shellSort(int[] a){int h = a.length / 2; //设置增量while(h >= 1){//比如10个数，0，5，1，6for(int i = h; i < a.length; i++){int temp = a[i]; //temp保存是否交换的值，后面的int j = i - h; //前面的 while(j >= 0 && a[j] > temp){ //大于交换a[j + h] = a[j];j -= h;//维护一下j}a[j + h] = temp;}h = h / 2;}}
}

希尔排序的复杂度和增量序列是相关的。空间复杂度：O(1) 稳定性：不稳定

希尔排序是按照不同步长对元素进行插入排序，当刚开始元素很无序的时候，步长最大，所以插入排序的元素个数很少，速度很快；当元素基本有序了，步长很小，插入排序对于有序的序列效率很高。所以，希尔排序的时间复杂度会比o(n^2)好一些。由于多次插入排序，我们知道一次插入排序是稳定的，不会改变相同元素的相对顺序，但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以shell排序是不稳定的。

五、归并排序

1、尽可能的一组数据拆分成两个元素相等的子组，并对每一个子组继续拆分，直到拆分后的每个子组的元素个数是 1 为止； 2、将相邻的两个子组进行合并成一个有序的大组； 3、不断的重复步骤2，直到最终只有一个组为止。

class MergeSort {public static void mergeArray(int[] a, int first, int mid, int last, int[] temp){//temp是一个空的存放排好序的数的数组int i = first, j = mid + 1;//设置两个数组的起始边界 first, mid + 1,结束边界为 mid 和 lastint k = 0;while(i <= mid && j <= last){if(a[i] <= a[j]){temp[k++] = a[i++];}else{temp[k++] = a[j++];}}while(i <= mid){//把左边剩余的元素移入数组temp[k++] = a[i++];}while(j <= last){//把右边剩余的元素移入数组temp[k++] = a[j++];}for(i = 0; i < k; i++){//把新数组中的数覆盖nums数组a[first + i] = temp[i];}}public static void mergeSort(int[] a, int first, int last, int[] temp){if(first < last){int mid = (first + last) / 2;mergeSort(a, first, mid, temp);//左边有序，直到每个序列的个数为1跳出递归mergeSort(a,mid + 1, last, temp);//右边有序mergeArray(a, first, mid, last, temp);//再将两个有序序列合并}}public static void main(String[] args) {int[] arr = {8, 4, 5, 7, 1, 3, 6, 2, 4};int[] temp = {0, 0, 0, 0, 0, 0, 0, 0, 0};mergeSort(arr, 0, arr.length - 1, temp);for(int i : arr){System.out.print(" " + i);}}
}

平均时间复杂度：O(nlogn) 最好情况：O(nlogn) 空间复杂度：O(n) 稳定性：稳定

归并排序是把序列递归地分成短序列，递归出口是短序列只有1个元素(认为直接有序)或者2个元素(1次比较和交换),然后把各个有序的段序列合并成一个有序的长序列，不断合并直到原序列全部排好序。可以发现，在1个或2个元素时，1个元素不会交换，2个元素如果大小相等也没有人故意交换，这不会破坏稳定性。那么，在短的有序序列合并的过程中，稳定是否受到破坏？没有，合并过程中我们可以保证如果两个当前元素相等时，我们把处在前面的序列的元素保存在结果序列的前面，这样就保证了稳定性。所以，归并排序也是稳定的排序算法。

六、快速排序

它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，

快速排序的本质就是把比基准数大的都放在基准数的右边,把比基准数小的放在基准数的左边,这样就找到了该数据在数组中的正确位置.然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

快速排序,说白了就是给基准数据找其正确索引位置的过程。

①先从队尾开始向前扫描且当low < high时,如果a[high] > tmp,则high–-,但如果a[high] < tmp,则将high的值赋值给low,即arr[low] = a[high],同时要转换数组扫描的方式,即需要从队首开始向队尾进行扫描了

②同理，当从队首开始向队尾进行扫描时,如果a[low] < tmp,则low++,但如果a[low] > tmp了,则就需要将low位置的值赋值给high位置,即arr[high] = arr[low],同时将数组扫描方式换为由队尾向队首进行扫描

③不断重复①和②,直到low>=high时(其实是low=high),low或high的位置就是该基准数据在数组中的正确索引位置

public class quickSort {public static void main(String[] args) {int[] array={6,1,2,7,9,3,4,5,8};quicksort(array, 0, array.length - 1);System.out.println(Arrays.toString(array));}public static void quicksort(int[] a,int low,int high){int low1=low;int high1=high;if(a.length<=1||low1>high1){return;}int base=a[low];//设置基准值，为数组的开头部分while(low1!=high1){//从右向左找小于base的while (a[high1]>=base&&high1>low1){high1--;}//从左向右找大于base的while(a[low1]<=base&&high1>low1){low1++;}//找到值后进行交换if(high1>low1){int temp=a[low1];a[low1]=a[high1];a[high1]=temp;}}//交换基准值a[low]=a[low1];a[low1]=base;quicksort(a,low,low1-1);quicksort(a,high1+1,high);}
}

优化可以采用随机base和三点取base

    public static void QSort(int[] a, int left, int right) {if (left > right) {return;}//三数中值分割法选取枢纽元int base = median3(a, left, right);int i = left;int j = right;while (i != j) {while (i < j && base >= a[i]) {i++;}while (i < j && base <= a[j]) {j--;}if (i < j) {swap(a, i, j);}}swap(a, i, right);QSort(a, left, i - 1);QSort(a, j + 1, right);}private static void swap(int[] a, int i, int j) {int temp = a[i];a[i] = a[j];a[j] = temp;}//三数中值分割法private static int median3(int[] a, int i, int j) {//对三个数进行排序int m = (i + j) >> 1;if (a[m] < a[i]) {swap(a, i, m);}if (a[j] < a[i]) {swap(a, i, j);}if (a[j] < a[m]) {swap(a, j, m);}//将枢纽元放在j - 1;swap(a, m, j);return a[j];}

快速排序的一次切分从两头开始交替搜索，直到 low 和 high 重合，因此，一次切分算法的时间复杂度为O(n),但整个快速排序的时间复杂度和切分的次数相关。

最优情况：每一次切分选择的基准数字刚好将当前序列等分。如果我们把数组的切分看做是一个树，那么上图就是它的最优情况的图示，共切分了logn次，所以，最优情况下快速排序的时间复杂度为O(nlogn)

最坏情况：每一次切分选择的基准数字是当前序列中最大数或者最小数，这使得每次切分都会有一个子组，那么总共就得切分n次，所以，最坏情况下，快速排序的时间复杂度为O(n^2)

平均情况：每一次切分选择的基准数字不是最大值和最小值，也不是中值，这种情况我们也可以用数学归纳法证明，快速排序的时间复杂度为O(nlogn)

空间复杂度：O(log n) 稳定性：不稳定

快速排序有两个方向，左边的i下标一直往右走，当a[i] <= a[center_index]，其中center_index是中枢元素的数组下标，一般取为数组第0个元素。而右边的j下标一直往左走，当a[j] > a[center_index]。如果i和j都走不动了，i <= j, 交换a[i]和a[j],重复上面的过程，直到i>j。交换a[j]和a[center_index]，完成一趟快速排序。在中枢元素和a[j]交换的时候，很有可能把前面的元素的稳定性打乱，比如序列为 5 3 3 4 3 8 9 10 11，现在中枢元素5和3(第5个元素，下标从1开始计)交换就会把元素3的稳定性打乱，所以快速排序是一个不稳定的排序算法，不稳定发生在中枢元素和a[j] 交换的时刻。
参考博客：图解快排

七、堆排序

前提知识：

堆是一个完全二叉树

完全二叉树有个特性：左边子节点位置 = 当前父节点的两倍 + 1，右边子节点位置 = 当前父节点的两倍 + 2

堆有最大堆、最小堆（或者称为大顶堆、小顶堆）

最大堆要求节点的元素都要不小于其左右孩子最小堆要求节点的元素都要不大于其左右孩子

堆虽然是一颗树，但是通常存放在一个数组中，父节点和孩子节点的父子关系通过数组下标来确定

小顶堆实现堆排序的过程：

public class HeapSort {public static void heapify(int[] arr){//1.构建堆for(int i = arr.length / 2 - 1; i >= 0; i--){//从最后的非叶子结点从下至上，从右至左调整结构adjustHeap(arr, i , arr.length);}//2.调整堆结for(int j = arr.length - 1; j > 0; j--){int temp = arr[0];arr[0] = arr[j];arr[j] = temp;//将堆顶元素与末尾元素进行交换adjustHeap(arr,0, j);//重新对堆进行调整}}//调整堆。可以通过改变if里面的条件实现大顶堆和小顶堆public static void adjustHeap(int[] arr, int i, int length){int temp = arr[i];//先取出当前元素ifor(int k = i * 2 + 1; k < length; k = k * 2 + 1){//从i结点的左子结点开始，也就是2i+1处开始if(k + 1 < length && arr[k] < arr[k + 1]){//如果左子结点小于右子结点，k指向右子结点k ++;}if(arr[k] > temp){//如果子节点大于父节点，将子节点值赋给父节点（不用进行交换）arr[i] = arr[k];i = k;}else{break;}}arr[i] = temp;//将temp值放到最终的位置}public static void main(String []args){int []arr = {4, 3, 2, 8, 6, 1};heapify(arr);System.out.println(Arrays.toString(arr));}
}

平均时间复杂度：O(nlogn) 最好情况：O(nlogn) 空间复杂度：O(1)

稳定性：不稳定