各种排序

冒泡排序

比较相邻的元素。如果第一个比第二个大，就交换他们两个。对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。只要进行n-1趟排序 public void bubble_sort(int[] arr) { int temp, len = arr.length; for (int i = 0; i < len - 1; i++){ for (int j = 0; j < len - 1 - i; j++){ if (arr[j] > arr[j + 1]) { temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; } } } }

注意两个循环的判断条件，len-1与len-1-i。

稳定平均时间复杂度：O(n2)最好时间复杂度：O(n)

选择排序

在要排序的一组数中，选出最小（或者最大）的一个数与第1个位置的数交换；然后在剩下的数当中再找最小（或者最大）的与第2个位置的数交换，依次类推，直到第n-1个元素（倒数第二个数）和第n个元素（最后一个数）比较为止。

public void select_sort(int[] arr) { int temp, len = arr.length; for (int i = 0; i < len - 1; i++){ int min = i; for (int j = i+1; j < len; j++){ if (arr[j] < arr[min]) { min = j; } } temp = arr[min]; arr[min] = arr[i]; arr[i] = temp; } } 不稳定时间复杂度与输入无关。 当i=1时，需进行n-1次比较；当i=2时，需进行n-2次比较；依次类推，共需要进行的比较次数是(n-1)+(n-2)+…+2+1=n(n-1)/2交换次数：n平均时间复杂度：O(n2)最好时间复杂度：O(n2)

插入排序

插入排序是一种最简单直观的排序算法，它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。

public void insert_sort(int[] arr) { int len = arr.length; for(int i=1;i<len;i++){ int num = arr[i]; for(int j=i;j>0 && num<arr[j-1];j--){ arr[j] = arr[j-1]; } arr[j] = num; } } 稳定交换次数与数组中倒置元素的数量相同最好情况下N-1次比较和0次交换平均时间复杂度：O(n2)最好时间复杂度：O(n)

希尔排序

插入排序的变种，但是非稳定.

希尔排序是基于插入排序的以下两点性质而提出改进方法的：

插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率。但插入排序一般来说是低效的，因插入排序每次只能将数据移动一位。

希尔排序的基本思想是：根据某个步长将数据分为几个部分分别排列，最后就是在基本有序的基础上进行插入排序，性能较高。

public void shell_sort(int[] arr){ int len = arr.length; int gap = 1; while(gap<len/3) gap = 3*gap+1; for(;gap>0;gap/=3){ for(int i = gap;i<len;i++){ int num = arr[i]; for(int j=i;j>0 && num<arr[j-gap];j-=gap){ arr[j] = arr[j-gap]; } arr[j] = num; } } } 不稳定时间复杂度受步长（增量）的影响平均时间复杂度：O(n^1.3)最好时间复杂度：O(n)最坏时间复杂度：O(n2)

归并排序

归并（Merge）排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。

将数组分为最小序列（每个序列中只有1个），然后两两进行归并排序，紧接着再将排序过的2个一组的序列再进行归并排序……

public void merge_sort(int[] arr,int[] res,int start,int end){ if(start>=end) return; int mid = start+(end-start)/2; int start1 = start, end1 = mid; int start2 = mid+1, end2 = end; merge_sort(arr,res,start,mid); merge_sort(arr,res,mid+1;end); int i = start; while(start1<=end1 && start2<=end2){ if(arr[start1]<arr[start2]){ res[i++] = arr[start1++]; }else{ res[i++] = arr[start2++]; } } while(start1<=end1){ res[i++] = arr[start1++]; } while(start2<=end2){ res[i++] = arr[start2++]; } for(int i=start;i<=end;i++){ arr[i] = res[i]; } } 稳定空间复杂度O(n)平均时间复杂度O(nlogn) -

快速排序

从数列中挑出一个元素，称为 “基准”（pivot），重新排序数列，所有比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面。这个过程结束后，该基准就处于其正确的位置上。这个称为分区（partition）操作。递归地进行上面两步

传统实现方法

public void quick_sort(int[] arr, int lo, int hi){ int num = arr[lo]; int i = lo,j = hi+1; while(true){ while(arr[++i]<num){ if(i == hi) break; } while(arr[--j]>num){ if(j == lo) break; } if(i>=j) break; int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } arr[lo] = arr[j]; arr[j] = num; quick_sort(arr,lo,j-1); quick_sort(arr,j+1,hi); } 不稳定平均时间复杂度：O(nlogn)最差时间复杂度 Ο(n2)　

堆排序

堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。

堆排涉及两个操作：

建堆：从第一个非叶子结点开始，使用下沉操作来建堆每次移除堆顶元素，并将其堆尾元素移至堆顶，并重新调整堆 //建堆 public void heapSort(int[] arr){ //从第一个非叶子结点开始建堆 int last = arr.length-1; int index = (last-1)/2; for(int i=index;i>=0;i--){ maxifyHeap(arr,i,arr.length-1); } //每次将堆顶元素与堆尾元素交换，并重新建堆 for(int i=arr.length-1;i>0;i--){ int temp = arr[0]; arr[0] = arr[i]; arr[i] = temp; maxifyHeap(arr,0,i-1); } } //调整堆，下沉过程 public void maxifyHeap(int[] arr,int i, int size){ int l_index = i*2+1; while(l_index<size){ int maxChild = arr[l_index]; int max_index = l_index; int r_index = l_index+1; if(r_index<size){ int right = arr[r_index]; if(right>maxChild){ maxChild = right; max_index = r_index; } } if(maxChild>arr[i]){ arr[max_index] = arr[i]; arr[i] = maxChild; i = max_index; l_index = i*2+1; }else break; } } 不稳定平均时间复杂度O(nlogn)适用于找最大/最小的k个数

桶排序

设置一个定量数组为空桶按照一定规则将待排序元素放入桶中每个桶中的元素都是排过序的，通常将元素放入桶中时对桶中元素进行排序依次从桶中取出元素即为有序序列

性质：

稳定时间复杂度O(n)空间复杂度O(m)

平均情况下桶排序以线性时间运行

计数排序

https://visualgo.net/en/sorting

稳定时间复杂度O(n+m)空间复杂度O(n+m)

其中m数据的最大值减最小值

基数排序

按位数进行桶排序，一共10个桶。 首先按个位数桶排序，从桶中取出后再按十位数排……

时间复杂度O(n*k)，k为最多的位数