柚子快报激活码778899分享：数据结构 十大经典排序算法
十大经典排序算法
文章目录
十大经典排序算法一、冒泡排序（bubble sort）二、选择排序 (Selection Sort)三、插入排序 (Insertion Sort)四、希尔排序(Shell Sort)五、归并排序(Merge Sort)六、快速排序 (Quick Sort)七、堆排序 (Heap Sort)八、计数排序 (Counting Sort)九、桶排序 (Bucket Sort)十、基数排序 (Radix Sort)
网上有很多算法思路，我在文中没有赘述，只是将代码复现了一遍。代码中注释了很多实现上的细节，如果你对代码细节方面有疑问，欢迎参考。
上图存在错误：
插入排序的最好时间复杂度为
O
(
n
)
O(n)
O(n)而不是
O
(
n
2
)
O(n^2)
O(n2)。希尔排序的平均时间复杂度为
O
(
n
l
o
g
n
)
O(nlogn)
O(nlogn)。
文中图片来自：十大经典排序算法总结 | JavaGuide
一、冒泡排序（bubble sort）
算法思路：
遍历数组，比较相邻的两个元素，若前一个元素大于后一个元素，交换这两个元素。继续比较下两个元素。每次遍历可以找出一个最大值，遍历length-1次即可
算法实现：
/**
* 冒泡排序
* @param arr
*/
public static void bubbleSort(int[] arr){
//i只是限定了冒泡的次数，每轮冒泡至少可以找出一个最大值，并将其排在最后，只需要循环length-1次就可以
for (int i = 1; i < arr.length; i++) {
boolean flag=true;
//内层循环只需要遍历到length-i，后i个元素已经是排好序的
for (int j = 0; j < arr.length - i; j++) {
if (arr[j]>arr[j+1]){
int temp=arr[j];
arr[j]=arr[j+1];
arr[j+1]=temp;
//用一个标志来表示本次循环是否修改顺序，若没有修改，说明数组已经排好序，不需要再继续下去
flag=false;
}
}
if(flag){
break;
}
}
}
二、选择排序 (Selection Sort)
算法思路：
循环length-1次，每次找出一个最小元素的下标，跟对应位置元素交换
算法实现：
/**
* 选择排序
* @param arr
*/
public static void selectionSort(int[] arr){
//遍历length-1次即可
for (int i = 0; i < arr.length-1; i++) {
//直接初始化minIndex为i
int minIndex=i;
//从i+1开始
for (int j = i+1; j < arr.length; j++) {
//若当前元素小于minIndex元素，只需修改minIndex为j
if(arr[j] minIndex=j; } } //如果minIndex就是i，那么不需要修改 if(minIndex!=i){ int temp=arr[i]; arr[i]=arr[minIndex]; arr[minIndex]=temp; } } } 不稳定原因：选择排序是给每个位置选择当前元素最小的，比如给第一个位置选择最小的，在剩余元素里面给第二个元素选择第二小的，依次类推，直到第n-1个元素，第n个元素不用选择了，因为只剩下它一个最大的元素了。那么，在一趟选择，如果一个元素比当前元素小，而该小的元素又出现在一个和当前元素相等的元素后面，那么交换后稳定性就被破坏了。 举个例子，序列arr = [5 8 5 2 9]，我们知道第一遍选择第1个元素5会和2交换，那么原序列中两个5的相对前后顺序就被破坏了，所以选择排序是一个不稳定的排序算法。 ———————————————— 版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。 原文链接：https://blog.csdn.net/qq_45795744/article/details/121353099 三、插入排序 (Insertion Sort) 算法思路： 遍历数组，对于每个元素，向前找到合适的位置插入 算法实现： /** * 插入排序 * @param a */ public static void insertionSort(int[] a) { //[0,i)是已经排好序的，i是待插入元素 for (int i = 1; i < a.length; i++) { int current = a[i]; int preIndex = i - 1; //如果当前元素小于前一个元素，将前一个元素后移至当前元素，直到找到current应在的位置 while (preIndex >= 0 && current < a[preIndex]) { a[preIndex + 1] = a[preIndex]; preIndex--; } a[preIndex + 1] = current; } } 四、希尔排序(Shell Sort) 算法思路： 插入排序的改进算法，采用了分治的思想，不是挨个比较插入，而是每隔gap进行比较插入，每一轮结束后gap减倍，直至gap为0 第一批突破 n 2 n^2 n2复杂度的算法 算法实现： /** * 希尔排序 * @param a */ public static void shellSort(int[] a) { int n=a.length; //类似于插入排序，但是插入比较的时候，是每隔一个gap的元素进行比较和插入 int gap=n/2; //这样最外层循环只有logn次 while(gap>0) { for (int i = gap; i < n; i++) { int current=a[i]; int preGapIndex=i-gap; while(preGapIndex>=0&¤t a[preGapIndex+gap]=a[preGapIndex]; preGapIndex-=gap; } a[preGapIndex+gap]=current; } gap/=2; } } 五、归并排序(Merge Sort) 算法思路： 采用分治思想，将数组两两拆分后再两两拆分···，然后利用双指针一一合并、两两合并、四四合并··· 算法实现： /** * 归并排序 * @param a * @return */ public static int[] mergeSort(int[] a){ //长度小于等于1返回 if(a.length<=1){ return a; } int mid=a.length/2; int[] array1=Arrays.copyOfRange(a,0,mid); int[] array2=Arrays.copyOfRange(a,mid,a.length); //分治，递归 return merge(mergeSort(array1),mergeSort(array2)); } public static int[] merge(int[] array1,int[] array2){ //将array1与array2归并排序，双指针 int p=0,p1=0,p2=0; int l1=array1.length,l2=array2.length; int[] sortedArray=new int[l1+l2]; while(p1 if(array1[p1] sortedArray[p++]=array1[p1++]; }else{ sortedArray[p++]=array2[p2++]; } } while(p1 sortedArray[p++]=array1[p1++]; } while(p2 sortedArray[p++]=array2[p2++]; } return sortedArray; } 六、快速排序 (Quick Sort) 算法思路： 找一个基准元素（一般为首元素或尾元素），将小于基准元素的排在其左边，小于基准元素的排在其右边，然后分别对左右部分递归进行快速排序 算法实现： /** * 快速排序 * @param arr * @param start * @param end */ public static void quickSort(int[] arr,int start,int end){ if(start>=end) return; int base=arr[start]; //以首元素为基准，同时暂存首元素，把位置空出来一边后续存储找到的比基准小的元素 int left=start,right=end; //左右指针 //从右往左找小于基准的元素，从左往右找大于基准的元素 while(left //先从右往左找，因为现在首元素位置可以使用，可以存储小于基准的元素 while(left right--; } arr[left]=arr[right]; //把arr[right]放到arr[left]之后，right位置又空缺出来，接下来从左往右找大于基准的元素，然后放在right处 while(left left++; } arr[right]=arr[left]; } //最后left等于right，并且位置空出来，再把base放在这里 arr[left]=base; quickSort(arr,start,left-1); quickSort(arr,left+1,end); } 七、堆排序 (Heap Sort) 堆参考：数据结构——堆（带图详解） 堆的逻辑结构是一颗满二叉树（除了最后一层外，其余每一层的节点数都达到最大值，并且最后一层的节点都集中在树的左部），同时满足父节点的值总是不小于其子节点（大顶堆），或不大于其子节点（小顶堆）的值。堆的存储结构是一个数组，也就是说将堆按照完全二叉树的顺序存储在一个一维数组中，下标满足：leftChild=parent*2+1, rightChild=parent*2+2 堆的构建、插入、删除、向下调整参考链接。 算法思路： 将数组构建为大顶堆，然后交换大顶堆（不是数组）首尾元素，然后将未排元素重新调整为大顶堆，重复上述操作。在这个过程大顶堆元素的数量每轮循环减一 算法实现： /** * 堆排序 * @param array */ public static void heapSort(int[] array){ //将数组构建为大顶堆 buildMaxheap(array); //记录堆的长度，后面很重要 int heapLength=array.length; while(heapLength>1){ //不停交换堆顶元素与堆尾元素，然后重新向下调整堆 int temp=array[0]; array[0]=array[heapLength-1]; array[heapLength-1]=temp; heapLength--; shiftDown(array,0,heapLength); } } //构建大顶堆 public static void buildMaxheap(int[] array){ //从倒数第一个非叶子结点开始，往前对每一个结点进行向下调整 for(int i=array.length/2-1;i>=0;i--){ shiftDown(array,i,array.length); } } //heapLength的作用是：在堆排序的时候，原理是不停的交换堆顶最大元素与末尾元素， // 然后重新将堆向下调整为最大堆，末尾已排好序的元素就不在堆里了，因此再向下调整的时候不能将其考虑在内 public static void shiftDown(int[] array, int parent, int heapLength){ int child=parent*2+1; //将较小元素不断下沉 while(child //找出较大的子节点 if(child+1 child=child+1; //若父节点大于较大子节点，说明已经调整好 if(array[parent]>=array[child]) break; else{ int temp=array[parent]; array[parent]=array[child]; array[child]=temp; } //继续向下 parent=child; child=parent*2+1; } } 八、计数排序 (Counting Sort) 算法思路： 直接将所有待排序元素的数值映射到数组对应下标的位置，若有重复元素加一即可。需要大量空间，适合类似0-100的小范围数值排序 算法实现： /** * 计数排序 * @param arr */ public static int[] countingSort(int[] arr){ //找出最大值最小值，以缩小count数组空间 int max=arr[0],min=arr[0]; for (int i : arr) { if(i>max) max=i; if(i } int[] count=new int[max-min+1]; int[] res=new int[arr.length]; //直接用arr[i]的值当count的索引，这里为了节省空间，将每一个值都减去最小值 for (int i = 0; i < arr.length; i++) { count[arr[i]-min]++; } //count维护完成之后实际上就可以直接遍历count填充res数组进行简单的排序了，比如待排序的数组是int型的 //但是假如待排序的数组是一个复杂的数据结构或是对象，比如一个Person对象，按照年龄排序，有两个person年龄相同，只凭借目前的count是无法决定对哪一个person先排序的 //简单地说，就是无法保证排序的稳定性。 //因此需要对count变形，使得count[i]存储的值表示小于等于元素i的元素个数。这一操作就相当于记录了包括i在内，i前面有多少个元素，这样就可以直接确定待排序数组每个元素最终的位置 //仅仅这样还是无法保证稳定性的，还需要下面的反向填充 for (int i = 1; i < count.length; i++) { count[i]+=count[i-1]; } //反向遍历待排序数组，填充res //由于count[i]存储的值表示小于等于元素i的元素个数，每次填充完一个元素才会对count--，这就导致对于两个相同的元素，先填充的元素结果放在了后面的位置，因此需要反向填充，把本来就在后面的放在后面 for (int i = arr.length-1; i >=0; i--) { res[count[arr[i]-min]-1]=arr[i]; count[arr[i]-min]--; } return res; } 九、桶排序 (Bucket Sort) 算法思路： 将待排序元素通过函数映射到桶中，这里采用的是均匀划分映射，然后对元素个数大于1的桶递归排序，或者使用其他排序算法进行排序。最后按顺序取出桶里的元素放回数组 算法实现： /** * 桶排序 * @param arr * @param bucketSize * @return */ public static List if(arr.size()<2||bucketSize==0) return arr; int max=arr.get(0),min=arr.get(0); for (Integer i : arr) { if(i>max) max=i; else if(i } //桶的数量应该由数据的范围决定,+1相当于向上取整 int bucketCount=(max-min)/bucketSize+1; List for (int i = 0; i < bucketCount; i++) { buckets.add(new ArrayList } //桶的下标从零开始，因此这里不用加一 for (Integer i : arr) { int bucketId=(i-min)/bucketSize; buckets.get(bucketId).add(i); } for (List //对于元素数量大于1的桶，递归排序 if(bucket.size()>1){ bucket=bucketSort(bucket,bucketSize/2); } } List for (List res.addAll(bucket); } return res; } 十、基数排序 (Radix Sort) 算法思路： 先按照低优先级位（属性）进行排序，再按照高优先级位（属性）排序。在按照某一位进行排序时，将相同的元素按顺序放入桶中。最后再按顺序从桶中取出。 算法实现： /** * 基数排序 * @param arr * @return */ public static int[] radixSort(int[] arr){ if(arr.length<2) return arr; int N=1; int max=arr[0]; for (int i : arr) { if(i>max) max=i; } //获取数组元素最高位数 while(max/10!=0){ max/=10; N++; } //先按照个位数排好序，再将按个位数排好序的数组按十位数排序，以此类推，最终得到的就是有序的数组 //若待排元素是其他类型的数据，只要有多个比较的属性，可以先按照低优先级的属性排序，再按照高优先级的属性排序，以此类推 for (int i = 0; i < N; i++) { List for (int i1 = 0; i1 < 10; i1++) { radix.add(new ArrayList<>()); } for (int value : arr) { //获取元素对应位的数字，若没有这一位，就按0处理，全放在radix.get(0)这个桶里 int radixId=(value/(int)Math.pow(10,i))%10; radix.get(radixId).add(value); } int index=0; //将排好序的元素按顺序取出放回数组 for (List for (Integer integer : integers) { arr[index++]=integer; } } } return arr; } 柚子快报激活码778899分享：数据结构 十大经典排序算法 好文推荐
发表评论