各种排序算法总结(全面)

2024-07-04 00:32| 来源: 网络整理| 查看: 265

目录冒泡排序改进的冒泡排序(鸡尾酒排序)选择排序插入排序二分插入排序希尔排序快速排序归并排序堆排序计数排序基数排序桶排序测试代码基本概要

排序算法大体可分为两种：

一种是比较排序，时间复杂度O(nlogn) ~ O(n^2)，主要有：冒泡排序，选择排序，插入排序，归并排序，堆排序，快速排序等。另一种是非比较排序，时间复杂度可以达到O(n)，主要有：计数排序，基数排序，桶排序等。

下面给出常见比较算法的排序性能

排序方法平均情况最好情况最坏情况空间稳定性冒泡O(n2)O(n)O(n2)O(1)稳定简单选择排序O(n2)O(n2)O(n2)O(1)不稳定直接插入排序O(n2)O(n)O(n2)O(1)稳定希尔排序O(nlogn) ~ O(n2)O(n1.3)O(n2)O(1)不稳定堆排序O(nlogn)O(nlogn)O(nlogn)O(1)不稳定归并排序O(nlogn)O(nlogn)O(nlogn)O(n)稳定快速排序O(nlogn)O(nlogn)O(n2)O(logn)~O(n)不稳定另外在说一下关于排序算法的稳定性问题 :　排序算法稳定性的简单形式化定义为：如果arr[i] = arr[j]，排序前arr[i]在arr[j]之前，排序后arr[i]还在arr[j]之前，则称这种排序算法是稳定的。通俗地讲就是保证排序前后两个相等的数的相对顺序不变。（可以通过自定义比较函数来去除稳定性问题）

举例：对于冒泡排序，原本是稳定的排序算法，如果将记录交换的条件改成arr[i] >= arr[i + 1]，则两个相等的记录就会交换位置，从而变成不稳定的排序算法。

为了使下面的代码方便，这里贴出Swap函数，交换数组中某两个位置的值；

public static void swap(int[] arr,int i,int j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; }

或者这样:

public static void swap(int[] arr,int i,int j) { arr[i] = arr[i] ^ arr[j]; arr[j] = arr[i] ^ arr[j]; arr[i] = arr[i] ^ arr[j]; } 冒泡排序

冒泡排序是比较简单的排序算法，它的运作过程如下：

进行n-1次排序。每次排序从0~n-1-i(i是次数编号)，检查这个序列中的数，两两相邻的数，如果前面的大于后面的就将它们交换，这样使得大的数往后面走，每次冒泡就会将一个大的数往后面冒，从而达到目的。 /**冒泡排序(加入了判断是否已经排序了的boolean变量) */ public static void bubbleSort(int[] arr) { for(int end = arr.length-1; end > 0; end--){ boolean isSort = true; for(int i = 0; i swap(arr,i,i+1); isSort = false; } } if(isSort)break; } }

第二个优化 :

记录上一次最后交换的那个位置，下一轮交换只需要进行到这个位置即可； public static void bubbleSort2(int[] arr){ for(int end = arr.length-1; end > 0; end--){ int border = 0; for(int i = 0; i swap(arr, i, i+1); border = i+1; } } end = border; } } 鸡尾酒排序（改进的冒泡排序）

也叫做定向冒泡排序，它的改进在于同时的冒泡两边，从低到高，然后从高到低，相当于顺便把最小的数也冒泡到最前面这个方法比冒泡更加高效一点:

/**改进的冒泡排序(鸡尾酒排序) 就是把最大的数往后面冒泡的同时，　最小的数也往前面冒泡*/ public static void cocktailSort(int[] arr) { int L = 0,R = arr.length-1; while(L for(int i = 0; i for (int i = 1; i for (int i = 1; i for(int i = 1; i int mid = L + (R-L)/2; if(arr[mid] > key)R = mid - 1; else L = mid + 1; } //二分结束之后　L = 刚好大于key(不是等于)的那个位置 for(int j = i-1; j >= L; j--)arr[j+1] = arr[j]; arr[L] = key; } } 希尔排序

希尔排序使更高效的插入排序，它的思想在于，

把数组分成几块，每一块进行一个插入排序；而分块的依据在于增量的选择分好块之后，从gap开始到n，每一组和它前面的元素（自己组内的）进行插入排序；

每次和组内的元素比较完之后，最后的元素基本就是有序的了，希尔排序相对于插入排序的优势在于插入排序每次只能将数据移动一位，不过希尔排序时间复杂度的大小还是要取决于步长的合适度，另外希尔排序不是一种稳定的排序算法。在这里插入图片描述

//步长为n/2.... public static void shellSort2(int[] arr) { for(int gap = arr.length; gap > 0; gap /= 2) { //增量序列 for(int i = gap; i int gap = 0; for(; gap 0; gap = (gap-1)/3) { //增量序列 for(int i = gap; i if(arr == null || arr.length //直接选取 arr[L]作为pivot(中心点) int key = arr[L]; int pivot = L; for(int i = L+1; i 完全了按照arr[L]划分数组的目的 return pivot; }

第一个优化(随机快排) (解决划分数选取不好的问题) 上面的快速排序当选取的划分的元素(pivot = arr[L])很小(或者很大)，使得后面划分的数组极度的不平衡的时候，会将快速排序降到O(N2)，于是我们使用随机快排，即不是将arr[L]作为划分点，而是随机选取一个元素作为(pivot)：在这里插入图片描述

public static void quickSort(int arr[]){ if(arr == null || arr.length //直接选取 arr[L]作为pivot(中心点) int key = arr[L]; int pivot = L; for(int i = L+1; i 完全了按照arr[L]划分数组的目的 return pivot; }

第二个优化(双路快速排序)(解决重复元素多的问题) 当我们要排序的数组重复元素很多的情况下，还是会使得划分极其的不均匀: 在这里插入图片描述第一个解决的方法: 换一种划分的方式:

将 key的元素放在数组的两边，更准确的说是: 左端放的是 =key的元素；然后设置两个指针(一个从L开始，一个从R开始)，然后向中间靠拢，分别找到第一个>=key(左边)、 if(L >= R) return; swap(arr, L,L + (int)(Math.random() * (R-L+1))); //随机选取一个pivot int p = partition(arr,L,R); quickProcess(arr,L,p-1); quickProcess(arr,p+1,R); } private static int partition(int[] arr, int L, int R) { int key = arr[L]; int less = L + 1, more = R; while(true){ while(less key)more--; if(less >= more)// not less > more break; swap(arr, less++, more--); } swap(arr, L, more); // finally let L to the middle return more; }

第三个优化(三路快速排序)(更好的解决重复元素多的问题) 三路快排关键在于partion的过程(荷兰国旗问题)，也就是将一个数组按照某个数划分成三部分:

先从序列中选取一个数作为基数(key)；分区过程，将key的放在右边，=key放到中间；再对左右区间重复第二步，直到各区间只有一个数；返回的p数组中p[0]代表的是等于区域的左边界，p[1]代表的是等于区域的右边界；

过程: 在这里插入图片描述这里写图片描述

public static int[] partition(int[] arr,int L,int R,int num){ int less = L-1; //小于部分的最后一个数 int more = R+1; int cur = L; while( cur swap(arr,++less,cur++); //把这个比num小的数放到小于区域的下一个，并且把小于区域扩大一个单位 }else if(arr[cur] > num){ swap(arr,--more,cur); //把这个比num大的数放到大于去余的下一个，并且把大于区域扩大一个单位 //同时，因为从大于区域拿过来的数是未知的，所以不能cur++ 还要再次判断一下arr[cur] }else{// 否则的话就直接移动 cur++; } } return new int[]{less + 1,more - 1}; //返回的是等于区域的两个下标 }

荷兰国旗问题的一个经典应用题LeetCode75-Sort Colors。注意这里的快速排序就是partition更改的，默认将R中的最后一个作为划分(也可以用arr[L])．这里总结一下优化 (所有的优化都是为了划分的均匀):

这里实际上使用的是三路快排，这个是为了防止数组中有很多重复的元素；

使用的是随机快排，时间复杂度是概率级别的Ologn(防止数组近乎有序)；

注意下面我写了四种partition的过程，达到的效果是一样的，分别使用arr[L]和arr[R]来作划分，一些细节和边界的不同导致程序不同；

最终三路快排代码如下:

public static void quickSort(int arr[]){ if(arr == null || arr.length [0~1)*3 --> 0~2 int[] p = partition4(arr,L,R); // 分别用partition、partition2、partition3测试都可以 quickProcess(arr,L,p[0]-1); quickProcess(arr,p[1]+1,R); } /** * 划分函数,这里使用的是arr[R]来划分, 左边的都比arr[R]小，右边都比arr[R]大 * 返回的数组是中间相等的两个下标 */ public static int[] partition(int[] arr,int L,int R){ int cur = L, less = L-1, more = R; int key = arr[R]; while( cur less+1,more}; //当然如果没有相等的部分那less+1 = more } /**上面的简写方式**/ public static int[] partition2(int[] arr,int L,int R){ int less = L-1, more = R; //把最后这个数当作标准也可以使用第一个 while( L less+1,more}; //为什么不是 more-1,因为上面又交换了一个, 当然如果没有相等的部分那less+1 = more } /**正方向：按照 arr[L]来划分**/ public static int[] partition3(int[] arr, int L, int R){ int key = arr[L], cur = L+1; int less = L, more = R+1; // more在外面(R+1)，等下循环cur < more while(cur less, more-1}; } /**对比partition3的不同**/ public static int[] partition4(int[] arr, int L, int R){ int key = arr[L], cur = L+1; int less = L, more = R; // more = R，等下循环cur less, more}; //同样返回的也不同 } public static void swap(int[] arr,int a,int b){ int temp = arr[a]; arr[a] = arr[b]; arr[b] = temp; }

注意这里和荷兰国旗partitiion过程的不同:

这里写图片描述

注意最后的arr[more]和arr[R]的交换:

这里写图片描述

归并排序

归并排序也是分治法一个很好的应用，先递归到最底层，然后从下往上每次两个序列进行归并合起来，是一个由上往下分开，再由下往上合并的过程，而对于每一次合并操作，对于每一次merge的操作过程如下：

这里写图片描述

看下面的例子合并过程如下：在这里插入图片描述

public static void mergeSort(int[] arr) { if(arr == null || arr.length int[] help = new int[R-L+1]; int k = 0; int p1 = L,p2 = mid + 1; //while(p1 if(arr == null || arr.length int[] help = new int[R-L+1]; int k = 0; long sum = 0; int p1 = L,p2 = mid + 1; while(p1 help[k++] = arr[p1++]; }else { //arr[p1] > arr[p2] 此时p2都小于arr[p1,mid]之间的元素 sum += (mid-p1+1); //加上逆序数的个数 help[k++] = arr[p2++]; } } while(p1 if(L == R)return 0; int mid = L + ((R-L) >> 1); //这个是放置溢出 return mergeProcess(arr, L, mid) + mergeProcess(arr, mid+1, R) + merge(arr,L,mid,R); //左边的小和和右边的小和 } public static int merge(int[] arr, int L, int mid, int R) { int[] help = new int[R-L+1]; int i = 0,sum = 0; int p1 = L,p2 = mid + 1; while(p1 //如果arr[p1] < arr[p2] 则arr[p1] < arr[p2 ~ R] sum += arr[p1]*(R-p2+1); help[i++] = arr[p1++]; }else { help[i++] = arr[p2++]; } } while(p1 // 区间的个数，1..2..4..8 for(int i = 0; sz + i if(arr == null || arr.length siftDown(arr,0,size); swap(arr,0,--size); } } //上浮的过程 --> 把新插入的数调整为大根堆的过程 public static void siftUp(int[] arr,int i){ while(arr[i] > arr[(i-1)/2]){ swap(arr,i,(i-1)/2); i = (i-1)/2; } } //下沉的过程 --> 这个函数就是一个数变小了，往下沉的函数,改变的数为index 目前的自己指定的堆的大小为heapSize public static void siftDown(int[] arr,int i,int heapSize){ int L = 2*i+1; while(L if(arr == null || arr.length = 0; i--) siftDown(arr,i,size+1); swap(arr,0,size); while(size > 0){ siftDown(arr,0,size); swap(arr,0,--size); } } /**往下沉的函数,改变的数为index 目前的自己指定的堆的大小为heapSize */ public static void siftDown(int[] arr,int i,int heapSize){ int L = 2*i+1; while(L //从A[i] 开始往下调整 int L = 2*i+1; //左孩子的下标 int R = 2*i+2;//右孩子的下标 int maxIdx = i; if(L arr[maxIdx])maxIdx = L; if(R arr[maxIdx])maxIdx = R; if(maxIdx != i) { swap(arr,i,maxIdx); //把当前结点和它的最大(直接)子节点进行交换 siftDown(arr,maxIdx,size); //继续调整它的孩子 } } public static void heapSort2(int[] arr) { int size = arr.length - 1; for(int i = (size-1)/2; i >= 0; i--) siftDown(arr,i,size+1); swap(arr,0,size);//和最后一个数交换 while(size > 0){ siftDown(arr,0,size); swap(arr,0,--size); } } 计数排序

计数排序是一种非比较排序：

利用一个count数组，统计每个元素arr[i]出现的次数count[arr[i]]，count数组的大小代表的是能排序的元素的最大的值；然后让count数组中每一个元素count[i]等于其与他前面一项count[i-1]相加，这时候count[arr[i]]表示的值就是小于等于arr[i]的元素的个数，这时就找到了arr[i]在输出数组中的位置；最后通过反向填充目标数组tmp，将数组元素arr[i] 放在数组tmp的第count[arr[i]]个位置(下标为count[arr[i]]-1)，每放一个元素就将count[arr[i]]递减，可以确保计数排序的稳定性；

看一个例子这里写图片描述填充过程：

/** * 计数排序 count 统计数组， tmp 目标填充数组 * 空间复杂度开销大 */ public static void countSort(int[] arr,int RANGE) { /**数组中最大的元素不能超过 RANGE*/ int[] count = new int[RANGE + 1]; int[] tmp = new int[arr.length]; for(int i = 0; i 1,10,100}; //这里只排序总共有三位数,分别代表个位，十位，百位 return ( num / radix[d]) % 10; } //根据数组arr中每个元素的第d位数,来对整个arr数组排序 public static void lsdRadixSortInfo(int[] arr,int d) { int[] count = new int[10]; // 单独考虑每一个位的时候，数字都是从[0~9] int[] tmp = new int[arr.length]; for(int i = 0; i for(int d = 0; d int[] count = new int[10]; int[] tmp = new int[arr.length]; for(int i = 0; i int max = getMax(arr); for(int exp = 1; max / exp > 0; exp *= 10) //从低位到高位 lsdRadixProcess(arr,exp); } 桶排序

桶排序的原理可以分为一下三个步骤：

扫描序列，根据每个元素的值所属的区间(可以设置一个映射函数)，放入指定的桶中(顺序放置)。对每个桶中的元素进行排序，(使用其它排序算法或以递归方式继续使用桶排序）看下面对{ 29, 25, 3, 49, 9, 37, 21, 43 }进行桶排序这里写图片描述

因为每个桶各自的容量可能不同，所以也可以使用链表来储存，但是空间复杂度高；

这里写图片描述

下面的代码:

主要是利用计数排序找到每个桶的起始下标和终止下标，然后对每个桶进行系统的排序:mapToBucket()采用的是/ bucketNum(桶的个数) 的操作，如果对0 ~ 99排序就设置桶的个数为10个，如果是0~999就设置为100个…； public static final int bucketNum = 100; //桶的个数 0 ～ 9号桶 //桶排序 public static int mapToBucket(int x) { // 映射函数f(x) return x / bucketNum; } public static void bucketSort(int[] arr) { int[] count = new int[bucketNum]; // 计数数组，存放桶的边界信息 int[] tmp = new int[arr.length]; for(int i = 0; i int[] arr = new int[1000]; Random random = new Random(); for(int i = 0; i System.out.println("bad!"); System.out.println(arr[i-1] + " " + arr[i]); good = false; break; } } if(good)System.out.println("good!"); System.out.println(Arrays.toString(arr)); } 附C++部分代码 #include namespace SortTestHelper{ int *generateRandomArray(int n, int L, int R){ int *arr = new int[n]; srand(time(NULL)); for (int i = 0; i int posx = rand() % n; int posy = rand() % n; std::swap(arr[posx], arr[posy]); } return arr; } int *copyArray(int a[], int n){ int *arr = new int[n]; for (int i = 0; i for (int i = 0; i arr[i + 1]) return false; return true; } template void testSort(const std::string &sortName, void (*sort)(T[], int), T arr[], int n){ clock_t startTime = clock(); sort(arr, n); clock_t endTime = clock(); std::cout // n-1次 int border = 0; for(int i = 0; i std::swap(arr[i], arr[i+1]); border = i+1; } } end = border; // 下一次只交换到这里 } } template void selectionSort(T arr[], int n){ for(int i = 0; i for(int i = 0; i for(int i = 0; i T* help = new T[R-L+1]; int p1 = L, p2 = mid + 1, k = 0; // note p1 = 0 while(p1 __mergeSort(arr, 0, n-1); } template void mergeSortBU(T arr[], int n){ for(int sz = 1; sz // 对[i...i+sz-1]和[i+sz...i+2*sz-1]内归并 __merge(arr, i, i+sz-1, std::min(n-1, i+sz+sz-1)); // min防止越界 } } } // 对arr[l...r]部分进行partition操作 // 返回p, 使得arr[l...p-1] < arr[p] ; arr[p+1...r] > arr[p] template int __partition1(T arr[], int L, int R){ std::swap( arr[L] , arr[rand()%(R-L+1)+L] );// 随机在arr[l...r]的范围中, 选择一个数值作为标定点pivot T key = arr[L]; int pivot = L; for(int i = L+1 ; i srand(time(NULL)); // 设置随机种子 __quickSort1(arr, 0, n-1); } template int __partition2(T arr[], int L, int R){ std::swap( arr[L] , arr[rand()%(R-L+1)+L] );// 随机在arr[l...r]的范围中, 选择一个数值作为标定点pivot T key = arr[L]; int less = L+1, more = R; while(true){ while(less key) more--; if(less >= more) break; std::swap(arr[less++], arr[more--]); } std::swap(arr[L], arr[more]); return more; } template void __quickSort2(T arr[], int L, int R){ if( L >= R ) return; int p = __partition2(arr, L, R); __quickSort2(arr, L, p-1 ); __quickSort2(arr, p+1, R); } template void quickSort2(T arr[], int n){ srand(time(NULL)); // 设置随机种子 __quickSort2(arr, 0, n-1); } template int* __partition3(T arr[], int L, int R){ std::swap( arr[L] , arr[rand()%(R-L+1)+L] );// 随机在arr[l...r]的范围中, 选择一个数值作为标定点pivot T key = arr[L]; // 将arr[L]作为划分 int cur = L+1, less = L, more = R+1; // more 也可以写成R, 但是下面的程序要改 while(cur less, more-1}; } template void __quickSort3(T arr[], int L, int R){ if( L >= R ) return; int* p = __partition3(arr, L, R); __quickSort3(arr, L, p[0]-1); __quickSort3(arr, p[1]+1, R); } template void quickSort3(T arr[], int n){ srand(time(NULL)); // 设置随机种子 __quickSort3(arr, 0, n-1); } int main(int argc, char const **argv) { int n = 2000; int *arr1 = SortTestHelper::generateRandomArray(n,0,n); // SortTestHelper::testSort("BubbleSort", bubbleSort, arr1, n); // SortTestHelper::testSort("selectionSort", selectionSort, arr1, n); // SortTestHelper::testSort("insertSort", insertSort, arr1, n); // SortTestHelper::testSort("insertSort2", insertSort2, arr1, n); // SortTestHelper::testSort("mergeSort", mergeSort, arr1, n); // SortTestHelper::testSort("mergeSortBU", mergeSortBU, arr1, n); // SortTestHelper::testSort("quickSort1", quickSort1, arr1, n); // SortTestHelper::testSort("quickSort2", quickSort2, arr1, n); SortTestHelper::testSort("quickSort3", quickSort3, arr1, n); return 0; }

【本文地址】

公司简介

联系我们