普通的排序算法（平均时间复杂度为O(n2)）
插入排序
先上代码
public static void insertionSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
for (int i = 1; i < arr.length; i++) {
for (int j = i - 1; j >= 0 && arr[j] > arr[j + 1]; j--) {
swap(arr, j, j + 1);
}
}
}
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];
}
算法分析：
插入排序和打牌一样，手里的牌是有序的，抓到的牌放到合适的位置使之有序即可。
第一个if是保证代码的robustness,让代码更加健壮，这是一个很好的习惯。第一个for循环中i的位置是记录已经排序好的位置末尾的后一个待插入元素。i的初始值为1，因为第0个元素在最开始独立出现的时候就是排好序的（一共就一个元素，不需要排序了）。i不断增大的过程就是有序量增加的过程，标志着算法的进程加深。
第二个for循环中j的初始位置是i-1，也就是排好序的最后一个元素。在j–的过程中，相邻两个元素发生交换（通过swap函数实现数组元素的交换），直至arr[j]<=arr[j+1]。
注意：这里的swap函数用了异或写法，目的是位运算加快速度并且节省temp的空间。平凡写法是创建一个temp变量作为中间人交换，a=a+b;b=a-b;a=a-b;也受到和异或一样的问题困扰。问题在于，如果某种排序算法中有a[i]和a[i]自己交换，则千万不可以用异或的方式，因为这会使得a[i]变成0,也就是说使用异或交换的时候，两个待交换的变量的内存不能是同一片地址。
《算法导论》中对插入排序中第二个for循环实现略有不同，但本质一样，书中是用一个key变量保存了arr[i]，然后j=i-1;如果arr[j]>key&&j>=0,则arr[j+1]=arr[j];也就是不断地把数组元素往后移，直到arr[j]<=key,最后把key放入arr[j+1],因为此时j+1的位置是“空的”（准确地说是和arr[j+2]相等，是无效信息)。本质无异。
我还想说明一点，关于第一个for循环i的值的范围，有的地方是取头不取尾，有的地方取尾不取头，这个其实是根据循环不变量确定的。插入排序的循环不变量就是0到i-1都保持有序，并不是0到i-1都是其最终位置。所以i从1开始，并且要取到最末尾。而像选择排序则不同，选择排序选出最大或最小值之后那个值就是确定的，以最小值为例，i应该从0开始，循环条件为i<arr.length-1,去掉末尾，因为前面都取到对应位置，最后一个元素自然也就在它自己的位置上。
选择排序
先上代码
public static void selectionSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
for (int i = 0; i < arr.length - 1; i++) {
int minIndex = i;
for (int j = i + 1; j < arr.length; j++) {
minIndex = arr[j] < arr[minIndex] ? j : minIndex;
}
swap(arr, i, minIndex);
}
}
public static void swap(int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
算法分析：
顾名思义，选择排序是每次选一个最小的数字，放到i的位置。有了插入排序算法详细的介绍和剧透，选择排序显得很简单。
i是记录待排序的位置，循环不变量是0到i-1都是排序好的从小到大的。
这里i从0到小于arr.length-1在上面已经解释过。minIndex记录最小的值的下标，minIndex的初始值是i，一个个往后比较，如果有比arr[i]小的值则更新minIndex的值，然后交换。注意，这里minIndex有可能等于i，也就是说可能是swap(arr,i,i),根据之前的解释，这里就不能用异或swap。
冒泡排序
代码如下
public static void Bubblesort(int[] arr){
Boolean flag= false;
if (arr == null || arr.length<2 ) return;
for (int i = arr.length - 1; i>0 ; i--){
for (int j = 0; j < i; j++) {
if (arr[j] > arr[j + 1]) {
swap(arr, j, j + 1);
flag = true;
}
}
if (flag == false) return;
flag=false;
}
}
public static void swap ( int[] arr, int a, int b){
arr[a] = arr[a] ^ arr[b];
arr[b] = arr[a] ^ arr[b];
arr[a] = arr[a] ^ arr[b];
}
算法分析：
冒泡排序的核心思想是相邻两两交换使得最大数字到最后面去。冒泡这里外层for循环i从array.length-1开始，到1结束（i>0)，原因是i其实是执行次数，为了让其含有更多信息，我们让i为待排序的位置，每次都确定一个最大的数字，i递减。
第二层for循环则是从0开始到i-1两两比较，如果前比后大则交换。
我还设了一个flag的布尔类型变量，意为当某一轮比较发现没有前比后大的情况说明排序已完成。开始设为false，如果产生比较则设为true，如果没有则还是false,在第二层循环结束后判定flag的值并且维护flag为false。
高级排序
归并排序
先上代码
public static void Mergesort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
Mergesort(arr, 0, arr.length - 1);
}
public static void Mergesort(int[] arr,int L,int R){
if (L==R) return;
int mid=L+((R-L)>>1);
Mergesort(arr,L,mid);
Mergesort(arr,mid+1,R);
Merge(arr,L,mid,R);
}
public static void Merge ( int[] arr, int l, int mid, int r){
int i=0;
int p1=l;
int p2=mid+1;
int[] help= new int[r-l+1];
while(p1<=mid && p2<=r){
help[i++]= arr[p1]<arr[p2]? arr[p1++]:arr[p2++];
}
while (p1<=mid){
help[i++]=arr[p1++];
}
while (p2<=r){
help[i++]=arr[p2++];
}
for (i=0;i<help.length;i++){
arr[l+i]=help[i];
}
}
算法分析：
归并排序利用的是分治思想，把数组一分为二，分别递归排序后通过merge算法合并。
注意：我写的Mergesort存在方法重载，第一个Mergesort是保证Mergesort接口的简洁性和鲁棒性，第二个Mergesort是具体的分治递归；最后通过Merge函数，在辅助数组help的帮助下合并两个数组，可见归并排序需要额外空间，不是原址的。
这里求mid的时候是mid=L+((R-L)>>1);结果自然是精确的，好处是不会溢出因为L+R溢出，而且位运算更快
PS:归并排序还可以用于在nlogn时间复杂度内求逆序对和小和，我会在后面的博客中更新。但是这些代码需要略微进行修改。
堆排序
先上代码
public static void Heapsort(int[] arr){
bulid_heap(arr);
int len=arr.length;
for (int i = arr.length-1 ; i >=1 ; i--) {
swap(arr,0,i);
len--;
heapify(arr,0,len);
}
}
public static void bulid_heap(int[] arr){
for (int i=(arr.length-2)>>1;i>=0;i--){
heapify(arr,i, arr.length);
}
}
public static void heapify(int[] arr,int i,int len) {
while (i*2+1< len){
int maxIndex=i*2+1;
if (i*2+2<len && arr[i*2+2]>arr[i*2+1]){
maxIndex=i*2+2;
}
if (arr[i]>=arr[maxIndex]) return;
else{
swap(arr,i,maxIndex);
i=maxIndex;
}
}
}
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];
}
算法分析：
使用大顶（根）堆，通过建堆和维护最大堆的性质使得arr[0]永远是数组中最大的数字，每次将0和最后一个数字交换，并且把堆的长度缩小一个单位，并且维护最大堆的性质，如此往复，最后可以得到从小到大排序的数组。
swap从怂起见还是用temp为好，我个人用异或结果最后将arr[0]和arr[0]自身交换，导致第一个数字总是0，最后改写循环终止条件到arr[1]才解决问题。
heapify是自上而下的过程，注意判断终止条件，i2+1如果超过了堆的长度（小心，堆的长度不一定是数组的长度，所以函数参数表中还有len）i2+2就更无从谈起，这说明i是叶节点。值得注意的是，如果产生交换，i要移到被交换的那个下一个位置，也就是maxIndex的位置，如果i自己最大，则直接跳出，说明已经完成大顶堆性质的维护。这个过程可以用递归，代码会更简洁易懂，但是我认为直接while更好。
build_heap函数是初始化建立大顶堆的过程，《算法导论》指出，只要从第一个不是叶节点的元素开始维护大顶堆的性质即可，自下而上建堆。由于left=i2+1,right=i2+2,所以父节点是(i-1)/2,我们只要从最后一个元素的父节点开始，逐个递减地往上建堆即可。即(arr.length-2)>>1。
下面是左神的代码，他考虑了一个个给出数字的情况，额外添加了heapInsert函数
public static void heapSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
for (int i = 0; i < arr.length; i++) {
heapInsert(arr, i);
}
int size = arr.length;
swap(arr, 0, --size);
while (size > 0) {
heapify(arr, 0, size);
swap(arr, 0, --size);
}
}
public static void heapInsert(int[] arr, int index) {
while (arr[index] > arr[(index - 1) / 2]) {
swap(arr, index, (index - 1) /2);
index = (index - 1)/2 ;
}
}
public static void heapify(int[] arr, int index, int size) {
int left = index * 2 + 1;
while (left < size) {
int largest = left + 1 < size && arr[left + 1] > arr[left] ? left + 1 : left;
largest = arr[largest] > arr[index] ? largest : index;
if (largest == index) {
break;
}
swap(arr, largest, index);
index = largest;
left = index * 2 + 1;
}
}
public static void swap(int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
heapInsert值得解释，虽然它和heapify是相同性质，但由于父节点只有一个，子节点却有两个，所以形式上heapInsert会简单很多，注意：heapInsert的终止条件是index等于0或者arr[index]小于等于arr[(index-1)/2]，左神只写了一句while(arr[index] > arr[(index - 1) / 2]),包括后者，其实也包括了前者，因为index=0的时候，(index-1)/2也为0（java中的除法是取整除法，1.5->1,-1.5->-1），非常精妙。
快速排序
先导问题:荷兰国旗问题。
1.简单版：将一个数组排序，使得<k的值在左侧的连续一片，其他的值在数组右侧。
2.升级版：将一个数组排序，使得<k的值在左侧的连续一片，==k的值在数组中间的连续一片，>k的值在数组的右边。（像荷兰的国旗一样三个不同颜色，其实法国国旗更贴切）
直接上升级版问题的代码：
public static void flagsort(int[] arr,int k){
int mark1=-1;
int mark2= arr.length;
int i=0;
while(i<mark2) {
if (arr[i]<k){
swap(arr,i++,++mark1);
}else if(arr[i]==k){
i++;
}else{
swap(arr,i,--mark2);
}
}
}
public static void swap(int[] arr,int i,int j){
int tmp=0;
tmp=arr[i];
arr[i]=arr[j];
arr[j]=tmp;
}
算法分析：
mark1是小于k的边界的下标，mark2是大于k的边界的下标。我们所做的事情就是遍历数组，如果arr[i]小于k则将其与小于k的边界的后面一个元素交换，并且维护mark1的值。如果是等于k，就直接继续遍历，如果大于k，则将arr[i]与大于k的边界的前面一个元素交换，但是注意i不能++，即不继续遍历，因为交换过来的元素我们尚不清除它和k的大小关系。
注意两件事：
1.swap函数不能用异或，因为会有重复地址的可能。
2.mark1或者2的边界是包括对应性质的边界，边界外的不包括其对应性质。
为了和让快排用上我们的函数接口，左神把函数修改了一下。
public static int[] partition(int[] arr, int l, int r, int p) {
int less = l - 1;
int more = r + 1;
while (l < more) {
if (arr[l] < p) {
swap(arr, ++less, l++);
} else if (arr[l] > p) {
swap(arr, --more, l);
} else {
l++;
}
}
return new int[] { less + 1, more - 1 };
}
public static void swap(int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
这样我们能得到返回的两个下标，表示边界的情况，还能对数组分块处理（参数列表中有l,r）。
快速排序就是选定一个数组中的k值交换到数组末尾（一般直接选取最后一个元素），然后将剩余部分排序，把k与大于k的边界的值交换即可达到分治目的。如果分类方法采取荷兰国旗问题的非升级版（这样的我们称之为1.0快排），当选取的k有很多出现的时候，算法就会比较慢，因为升级版问题（2.0快排）把等于k的值也分块排好，这样我们分治的范围就更小了（这就是为什么要返回一个两个元素的数组标记边界的位置）。
当然，我们还嫌这样不够，众所周知（我最近才知道）即使是2.0快排的最差情况排序时间复杂度仍然是O(n2),因为如果对于一个有序数组（如1 2 3 4 5 6 7 8 9），我们每次都选取最后一个元素，通过国旗问题算法分块事件复杂度是O(n),但是我们的分治并没有起到作用，我们的子问题是变成了对1到8排序，如此下来，就变成了O(n2)。
核心问题是我们每次都选取最后一个数字作为k会遇到难受的问题，解决方法是随便选k，通过概率模型将算法的统计学意义上的时间复杂度降低。
public static void quickSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
quickSort(arr, 0, arr.length - 1);
}
public static void quickSort(int[] arr, int l, int r) {
if (l < r) {
swap(arr, l + (int) (Math.random() * (r - l + 1)), r);
int[] p = partition(arr, l, r);
quickSort(arr, l, p[0] - 1);
quickSort(arr, p[1] + 1, r);
}
}
public static int[] partition(int[] arr, int l, int r) {
int less = l - 1;
int more = r;
while (l < more) {
if (arr[l] < arr[r]) {
swap(arr, ++less, l++);
} else if (arr[l] > arr[r]) {
swap(arr, --more, l);
} else {
l++;
}
}
swap(arr, more, r);
return new int[] { less + 1, more };
}
public static void swap(int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
Math.random()可以生成[0,1)之间的等概率的数（计算机上等概率，不是数学上的等概率，因为计算机精度有限）。可以通过l+(int)(Math.random()*(r-l+1))等概率地取得l到r之间的任意一个整数。其余比较基础，注意递归条件是r>l，不要反过来写（r==l则return之类的），因为过程中可能出现l<r，比如对开头的2，2，2，排序，l=0,mark1=-1,最后返回的r是-1<0。
希尔排序
先上代码
public static void shellsort(int[] arr){
for(int gap = arr.length>>1 ;gap>0; gap/=2){
for (int i = gap; i < arr.length; i++) {
for (int j = i;j>=gap && arr[j]<arr[j-gap];j-=gap ) {
swap(arr,j,j-gap);
}
}
}
}
public static void swap(int[] arr,int i,int j){
int tmp=arr[i];
arr[i]=arr[j];
arr[j]=tmp;
}
算法分析：
每次只对gap间隔的数组元素进行排序，如长度为10的数组gap=3时对下标为{0，3，6，9}和{1，4，7}以及{2，5，8}的三个子数组分别进行排序，然后二分缩小gap的值。
第一个循环就是对gap的值进行控制的总循环，注意gap初始值取arr.length/2即可，因为arr.length只有0满足，不需要排序。
第二个和第三个循环合起来保证相同gap下的不同数组排序好，我的代码中使用的是插入排序完成此过程，因为插入排序对我个人而言比较好理解，每一个新的元素在插入排序的过程中都能找到自己在子数组中目前的正确相对位置。所以不需要重复考虑，i从gap开始遍历数组，j从i开始不断和j-gap比较并且交换，j再以gap为公差递减至gap。最里层的循环保证了子数组当前的有序性，倒数第二层的循环保证了完备性。注意i,j的初始值和j的终止条件。也可以通过冒泡完成，但是那个我理解不太了。
如下是C语言实现shellsort并通过冒泡排序实现子数组排序的代码。
桶排序思想下的排序（不基于比较）
桶排序思想是一种不基于比较的排序，使用情况和数据状况有关。
计数排序
以空间换时间，适用于数据范围较窄的数据状况。如某地区人的年龄。
其本质是一种哈希，只不过哈希函数是本身，广义上来说只要哈希函数保证两个数的相对顺序不变（哈希函数离散地单调递增）即可。
public static void main(String[] args) {
int[] num = {2, 3, 4, 6, 3, 2, 5, 12, 2, 12, 12, 3, 45, 23, 12};
int[] record = count(num);
for (int i = 0; i < record.length; i++) {
while (record[i] > 0) {
System.out.println(i);
record[i]--;
}
}
}
public static int[] count(int[] arr){
int[] help = new int[150];
for (int i = 0; i < arr.length; i++) {
help[arr[i]]++;
}
return help;
}
以下为左神代码
public static void countSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
int max = Integer.MIN_VALUE;
for (int i = 0; i < arr.length; i++) {
max = Math.max(max, arr[i]);
}
int[] bucket = new int[max + 1];
for (int i = 0; i < arr.length; i++) {
bucket[arr[i]]++;
}
int i = 0;
for (int j = 0; j < bucket.length; j++) {
while (bucket[j]-- > 0) {
arr[i++] = j;
}
}
}
基数排序
数据能用进制表示，这里我们用十进制举例。
先将待排序元素处理成相同位数，即找到最高位数字，其余数字高位不足的补零。
有十个桶子，每个桶分别对应0,1,2…9。先考虑每个待排序元素的第一位（个位），从左往右依次放入个位数字对应的桶中。然后将其按照顺序从0号桶到9号桶倒出，同一个桶内的元素按队列处理，即先进先出，后进后出（FIFO）。然后考虑第二位（十位），重复上面操作。
算法分析：
由于最高位最后考虑，故最高位优先级最高。而先进先出原则没有违反同一个位数下的已经排好序部分的次序。所以算法是正确的，但是要准备这么多桶子总是很麻烦，我们采用等效的优化方式实现。
下面是左神的代码，我肯定现在写不出这么好的。
public static void radixSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
radixSort(arr, 0, arr.length - 1, maxbits(arr));
}
public static int maxbits(int[] arr) {
int max = Integer.MIN_VALUE;
for (int i = 0; i < arr.length; i++) {
max = Math.max(max, arr[i]);
}
int res = 0;
while (max != 0) {
res++;
max /= 10;
}
return res;
}
public static void radixSort(int[] arr, int begin, int end, int digit) {
final int radix = 10;
int i = 0, j = 0;
int[] bucket = new int[end - begin + 1];
for (int d = 1; d <= digit; d++) {
int[] count = new int[radix];
for (i = begin; i <= end; i++) {
j = getDigit(arr[i], d);
count[j]++;
}
for (i = 1; i < radix; i++) {
count[i] = count[i] + count[i - 1];
}
for (i = end; i >= begin; i--) {
j = getDigit(arr[i], d);
bucket[count[j] - 1] = arr[i];
count[j]--;
}
for (i = begin, j = 0; i <= end; i++, j++) {
arr[i] = bucket[j];
}
}
}
public static int getDigit(int x, int d) {
return ((x / ((int) Math.pow(10, d - 1))) % 10);
}
不得不感慨一句这个函数的封装要做好，我们不妨从getDigit函数开始分析，d是要得到的位数，x是待取位数的数字对象。x除以10的d-1次方，就可以让小数点前移d-1次，最后留下待取的数字为个位数。如果超过由于整数除法就直接为0（之前说高位不足补0），这里直接用pow函数取int就可以实现，我觉得很神奇，不过也算是学到了。最后记得模10取个位。
再分析maxbit函数，先通过遍历找出数组中最大的数字。然后不断除10直到为0，逻辑上res先++再max除10。
radixSort是核心部分，记录下一个常变量radix表示基底（进制）先建立一个bucket数组存放出桶的数字，大小和待排序数字元素个数相同。由于数字最高有几位就出入桶几次，所以最外层的d的for循环就是总的操作次数，并且d记录了目前操作的位数信息，即第几位。再建立一个count数组，数组大小和进制相等，如10进制就10个，意义对应0到9。然后遍历arr中待排序元素，分别取第d位的数字然后放入count中。再另起一个for循环对count进行处理，处理之后的结果是count[i]表示<=i的元素个数，这样求前缀和的方式让count数组实现了对bucket的分块，我们后面就会体现出来。
然后注意从右往左遍历arr数组，此时我们默认arr数组在d-1位及以前都是有序排列好的（循环不变量）。取出第i个元素的d位数字j，对应到count数组中的count[j]。把arr[i]填入bucket的第count[j]位置，也就是bucket[count[j] - 1] = arr[i];然后维护count[j]的值。这样的操作能使得出桶完成。然后将桶中的元素分别按顺序赋值给arr。
正确性分析：count起到了对bucket分段的作用，比如j为3，count[3]=5,现在从右往左遍历arr，会优先把j=3的d-1位及以内的更大的数字填入count[3]对应的位置（bucket[5-1]）。然后维护count[3]的值，因为下一个j==3的数字进来就要往左边靠了。重要的是这样不会影响j<3和j>3的值分块的正确性，j<=3无需置疑，count[3]–不会影响小于等于1或2的个数。而j=4或者更大的数字也不会受到影响，因为count[3]–的含义只是那个位置被占据，并不影响小于等于3的个数。所以分片正确性不变。