找出第i小的元素，与第i位置进行互换
void selection_sort(int*a,int n)
{
for(int i=1;i<=n;i++)
{
int mark=i;
for（int j=i+1;j<=n;j++)
if(a[j]<a[mark])
mark=j;
swap(a[i],a[mark]);
}
}
检查相邻元素，比较大小并交换，i次扫描后末尾/起始必为极值，此时n-1次扫描后数组遍历完毕，完成排序
优化：若从开始的第一队到结尾的最后一对，相邻元素没有进行交换，则在右边的元素总大于等于左边元素，此时已经有序，无需进行下去（flag)
void bubble_sort(int* a,int n) { bool flag=1; while(flag) { flag=0; for(int i=1;i<n;i++) { if(a[i]>a[i+1]) { flag=1; swap(a[i],a[i+1]); } } } }
桶排序的思想是若待排序的值在一个明显有限范围内(整型)时，可设计有限个有序桶，待排序的值装入对应的桶（当然也可以装入若干个值），桶号就是待排序的值，顺序输出各桶的值，将得到有序的序列
桶排序按下列步骤进行：
设置一个定量的数组当作空桶；
遍历序列，并将元素一个个放到对应的桶中；
对每个不是空的桶进行排序；
从不是空的桶里把元素再放回原来的序列中。
void bucket_sort() { cin>>n; for(int i=1;i<=n;++i) { cin>>x; a[x]++; } for(int i=1;i<=n;i++) while(a[i]>0) { a[i]--; cout<<i<<' '; } }//初级 public class BucketSort { public static int[] BucketSort(int[] arr) { if(arr == null || arr.length < 2) return arr; int n = arr.length; int max = arr[0]; int min = arr[0]; // 寻找数组的最大值与最小值 for (int i = 1; i < n; i++) { if(min > arr[i]) min = arr[i]; if(max < arr[i]) max = arr[i]; } //和优化版本的计数排序一样，弄一个大小为 min 的偏移值 int d = max - min; //创建 d / 5 + 1 个桶，第 i 桶存放 5*i ~ 5*i+5-1范围的数 int bucketNum = d / 5 + 1; ArrayList<LinkedList<Integer>> bucketList = new ArrayList<>(bucketNum); //初始化桶 for (int i = 0; i < bucketNum; i++) { bucketList.add(new LinkedList<Integer>()); } //遍历原数组，将每个元素放入桶中 for (int i = 0; i < n; i++) { bucketList.get((arr[i]-min)/d).add(arr[i] - min); } //对桶内的元素进行排序，我这里采用系统自带的排序工具 for (int i = 0; i < bucketNum; i++) { Collections.sort(bucketList.get(i)); } //把每个桶排序好的数据进行合并汇总放回原数组 int k = 0; for (int i = 0; i < bucketNum; i++) { for (Integer t : bucketList.get(i)) { arr[k++] = t + min; } } return arr; } }代码中，所有的桶保存在ArrayList集合当中，每一个桶被定义成一个链表（LinkedList<Double>），这样便于在尾部插入元素。
定位元素属于第几个桶，是按照比例来定位
(array[i] - min) * (bucketNum-1) / d
要定位元素 array[i] 在第几个桶，先减去最小值min,看它在桶数组（ArrayList）中的偏移为多少，然后除以桶的区间大小d/(buketNum-1),相当于乘以(buketNum-1)/d，除以桶区间大小就可以定位是在哪个桶里了。
同时，代码使用了JDK的集合工具类Collections.sort来为桶内部的元素进行排序。Collections.sort底层采用的是归并排序或Timsort，小伙伴们可以简单地把它们当做是一种时间复杂度 O（nlogn）的排序。
计数排序的工作原理是使用一个额外的数组C ，其中第i个元素是待排序数组A中值等于i的元素的个数，然后根据数组C来将A中的元素排到正确的位置。(初级桶排序）
它的工作过程分为三个步骤：
计算每个数出现了几次；
求出每个数出现次数的 前缀和；
利用出现次数的前缀和，从右至左计算每个数的排名。
public class Counting { public static int[] countSort(int[] arr) { int n = arr.length; int max = arr[0];// 寻找数组的最大值 for (int i = 1; i < n; i++) { if(max < arr[i]) max = arr[i]; }//创建大小为max的临时数组 int[] temp = new int[max + 1];//统计元素i出现的次数 for (int i = 0; i < n; i++) { temp[arr[i]]++; } int k = 0; for (int i = 0; i <= max; i++) { for (int j = temp[i]; j > 0; j--) { arr[k++] = i; } }//把临时数组统计好的数据汇总到原数组 return arr; } }
它的工作原理为将待排列元素划分为“已排序”和“未排序”两部分，每次从“未排序的”元素中选择一个插入到“已排序的”元素中的正确位置。
1、从数组第2个元素开始抽取元素。
2、把它与左边第一个元素比较，如果左边第一个元素比它大，则继续与左边第二个元素比较下去，直到遇到不比它大的元素，然后插到这个元素的右边。
3、继续选取第3，4，....n个元素,重复步骤 2 ，选择适当的位置插入。
void insertSort(int*a,int n) { for(int i=1;i<=n;i++) { int key=a[i]; int j=i-1; while(j>=0&&a[j]>key) j--； for(int k=i;k>j+01;k--) a[k]=a[k-1];//腾出位置准备插空 a[j+1]=key; } }
排序对不相邻的记录进行比较和移动：
将待排序序列分为若干子序列（每个子序列的元素在原始数组中间距相同）；
对这些子序列进行插入排序；
减小每个子序列中元素之间的间距，重复上述过程直至间距减少为 1。
希尔排序就是为了加快速度简单地改进了插入排序，交换不相邻的元素以对数组的局部进行排序。希尔排序的思想是采用插入排序的方法，先让数组中任意间隔为 h 的元素有序，刚开始 h 的大小可以是 h = n / 2,接着让 h = n / 4，让 h 一直缩小，当 h = 1 时，也就是此时数组中任意间隔为1的元素有序，此时的数组就是有序的了。
需要注意的是，对各个分组进行插入的时候并不是先对一个组排序完了再来对另一个组排序，而是轮流对每个组进行排序
input: an array a of length n with array elements numbered 0 to n − 1 inc ← round(n/2) while inc > 0 do: for i = inc .. n − 1 do: temp ← a[i] j ← i while j ≥ inc and a[j − inc] > temp do: a[j] ← a[j − inc] j ← j − inc a[j] ← temp inc ← round(inc / 2)
输入：1个长度为n的矩阵a，矩阵的编号从0到n - 1 整数inc从n / 2到1，每次循环inc变为inc / 2 i从inc到n - 1，每次循环i变为i + 1 将a[ i ]的值赋给temp j从i 到inc，每次循环j变为j - inc 如果a[ j − inc ]大于temp，则将a[ j - inc ]的值赋给a[ j ] 否则跳出j循环 j循环结束 将temp的值赋给a[ j ] i循环结束 inc循环结束
void shellsort(int*a) { int n=a.length; for(int gap=n/2;gap>=1;gap/=2)//Donald Shell推荐从n/2开始 for(int i=gap;i<n;i++) insertI(a,gap,i) //将a[i]插入在分组位置（排序） } void insertI(int *a,int gap,int i) { int inserted=a[i];//保存插入数 int j； for(j=i-gap;j>0&&inserted<a[j];j-=gap) a[k+gap]=a[k];//倒序比大小，将提取值往前插空（移位） a[k+h]=inserted; } void shell_sort(int arr[],int n) { int i,j,inc,key; //初始增量n/2 for(inc=n/2;inc>0;inc/=2) { //每趟插入排序 for(i=inc;i<n;i++) { key=arr[i]; for(j=i;j>=inc&&key<arr[j-inc];j-=inc) arr[j]=arr[j-inc]; arr[j]=key; } } }//分组插排
它的工作原理是将待排序的元素拆分为k个关键字（比较两个元素时，先比较第一关键字，如果相同再比较第二关键字……），然后先对第k关键字进行稳定排序，再对第k-1关键字进行稳定排序，再对第k-2关键字进行稳定排序……最后对第一关键字进行稳定排序，这样就完成了对整个待排序序列的稳定排序。
public static int[] radioSort(int[] arr) { if(arr == null || arr.length < 2) return arr; int n = arr.length; int max = arr[0];// 找出最大值 for (int i = 1; i < n; i++) { if(max < arr[i]) max = arr[i]; }// 计算最大值是几位数 int num = 1; while (max / 10 > 0) { num++; max/=10; } // 创建10个桶 ArrayList<LinkedList<Integer>> bucketList = new ArrayList<>(10); //初始化桶 for (int i = 0; i < 10; i++) { bucketList.add(new LinkedList<Integer>()); }// 进行每一趟的排序，从个位数开始排 for (int i = 1; i <= num; i++) { for (int j = 0; j < n; j++) { // 获取每个数最后第 i 位是数组 int radio = (arr[j] / (int)Math.pow(10,i-1)) % 10; //放进对应的桶里 bucketList.get(radio).add(arr[j]); }//合并放回原数组 int k = 0; for (int j = 0; j < 10; j++) { for (Integer t : bucketList.get(j)) { arr[k++] = t; }//取出来合并了之后把桶清光数据 bucketList.get(j).clear(); } } return arr; }
分治法的典型应用，将子序列合并得到完全有序序列
分解->合并
合并过程为：比较a[i]和a[j]的大小，若a[i]≤a[j]，则将第一个有序表中的元素a[i]复制到b[k]中，并令i和k分别加上1；否则将第二个有序表中的元素a[j]复制到r[k]中，并令j和k分别加上1，如此循环下去，直到其中一个有序表取完，然后再将另一个有序表中剩余的元素复制到r中从下标k到下标t的单元。归并排序的算法我们通常用递归实现，先把待排序区间[s,t]以中点二分，接着把左边子区间排序，再把右边子区间排序，最后把左区间和右区间用一次归并操作合并成有序的区间[s,t]。
//version1 void merge_sort(int s,int t) { if(s==t) return;//剩下一个数不排序 int mid=(s+t)/2; merge_sort(s,mid); merge_sort(mid,t); int i=s,j=mid+1,k=s; while(i<=mid&&j<=t) { if(a[i]<=a[j]) { r[k]=a[i]； k++; i++; }else { r[k]=a[j]; k++; j++; } while(i<=mid) { r[k]=a[i]; k++; i++; }//复制剩余序列 while(j<=t) { r[k]=a[j]; k++; j++; } for(int i=s;i<=t;i++) a[i]=r[i];//复制为有序列以便递归 } } //version2 void merge(int arr[],int tempArr[],int left,int mid,int right) { //标记左半区一个未排序元素 int l_pos=left; //标记右半区一个未排序元素 int r_pos=mid+1; //临时数组下标 int pos=left; //合并 while(l_pos<=mid&&r_pos<=right) { if(arr[l_pos]<arr[r_pos])//左半区第一个剩余元素更小 tempArr[pos++]=arr[l_pos++]; else tempArr[pos++]=arr[r_pos++]; } //合并左半区剩余元素 while(l_pos<=mid) tempArr[pos++]=arr[l_pos++]; //合并右半区剩余元素 while(r_pos<=right) tempArr[pos++]=arr[r_pos++]; //临时数组合并后元素复制回原来数组 while (left<=right) { arr[left]=tempArr[left]; left++; } } void msort(int arr[],int tempArr[],int left,int right) { //单元素不划分，认为有序，直接归并 if(left<right) { int mid=(left+right)/2; //递归划分左右半区 msort(arr, tempArr, left, mid); msort(arr, tempArr, mid+1, right); //合并选择区 merge(arr, tempArr, left, mid, right); } } void merge_sort(int arr[],int n)//入口 { //分配辅助数组 int* tempArr =(int*)malloc(n*sizeof(int)); if(tempArr)//成功分配 { msort(arr,tempArr,0,n-1); free(tempArr); } else { printf("error:failed to allocate memory"); } }
