常见的排序算法（Java实现）-笔记
冒泡排序
每次从剩余序列中相邻元素进行依次比较后拿出一个最大的数放在末尾。
//冒泡排序
public static void bubbleSort(int[] source){
boolean exchange;
for(int i=source.length-1;i>0;i--){
exchange = false;
for(int j = 0;j<i;j++){
if(source[j]>source[j+1]){
swap(source,j,j+1);
exchange = true;
}
}
if(!exchange)return;
}
}
最差平均为O(n^2),最好是O(n),此时已经有序。
选择排序
每次从剩余序列中选择元素中最小的放在开头。
public static void selectSort(int[] source){
for(int i=0;i<source.length;i++){
for(int j = i+1;j<source.length;j++){
if(source[i]>source[j]){
swap(source,i,j);
}
}
}
}
最差平均为O(n^2)。
插入排序
每次新加入一个元素和已有的元素比较，插入到合适的位置（左小右大），因为原有序列有序，所以排序后有序
//插入排序
public static void insertSort(int[] source){
for(int i=1;i<source.length;i++){
for(int j = i;j>0 && source[j]<source[j-1];j--){
swap(source,j,j-1);
}
}
}
最差平均为O(n^2),最好是O(n)。
二分排序
每来一个新数采用二分法在原有序列中找要插入的位置，然后将原序列下标比high大的元素后移，然后插入。
//二分排序
public static void twoClassSort(int[] a){
int mid;
for(int i=1;i<a.length;i++){
int temp = a[i];
int low = 0;
int high = i-1;
while(low<=high){
mid = (low+high)/2;
if(a[mid]>temp){
high=mid-1;
}else
low = mid+1;
}
for(int j = i-1;j>high;j--){
a[j+1]=a[j];
}
a[low] = temp;
}
}
O(n^2).
归并排序
分治的算法，将序列分成可排序的最小序列，排序之后再进行归并。
//归并排序
public static void mergeSort(int[] source,int start,int end){
if(start<end){
int mid = (start+end)/2;
mergeSort(source,start,mid);
mergeSort(source,mid+1,end);
merge(source,start,mid,mid+1,end);
}
}
public static void merge(int[] arr,int start1,int end1,int start2,int end2){
int i,j;
i=start1;
j=start2;
int k =0;
int temp[] = new int[end2-start1+1];
while(i<=end1 &&j<=end2){
if(arr[i]>arr[j]){
temp[k++]=arr[j++];
}else{
temp[k++]=arr[i++];
}
}
while(i<=end1){
temp[k++]=arr[i++];
}
while(j<=end2){
temp[k++]=arr[j++];
}
k=start1;
for(int element:temp){
arr[k++]=element;
}
}
最差平均最好都为O(nlog n).
shell排序
基本思想：先取一个小于n(n为记录数)的整数d1作为第一个增量，把待排记录分成d1个小组，所有距离为d1的倍数的记录放在同一组。最后一句有点难懂，看示例比较好理解。
int[] arr = new int[]{49,38,65,97,76,13,27,49};
比如这么一个数组，假设我们取d1=2，那么该数组元素就分为2组，(49,65,76,27)一组，剩余为另一组；若d1=3，那就分为3组，(49,97,27)、(38,76,49)、(65,13)三组，取其他值类推。
分好组之后，先在各组内进行直接插入排序(见上),然后取d2<d1(一般取dn+1=dn/2或dn/3+1)继续进行分组、插入排序......直到dn=1，即所有记录放在同一组中进行直接插入排序为止。
Java代码：
//shell排序
public static void shellSort(int[] source){
int j = 0;
int temp = 0;
for (int increment = source.length / 2; increment > 0; increment /= 2) {
System.out.println("increment:" + increment);
for (int i = increment; i < source.length; i++) {
temp = source[i];
for (j = i - increment; j >= 0; j -= increment) {
if (temp < source[j]) {
source[j + increment] = source[j];
} else {
break;
}
}
source[j + increment] = temp;
}
for (int i = 0; i < source.length; i++)
System.out.print(source[i] + " ");
System.out.println();
}
}
O(nlog n)。shell排序是不稳定的。两个相同记录在排序前后的相对次序会发生变化。
快速排序
基本思想：设待排区为R[low...high]，快排的思想如下：
(1)分解
在R[low...high]中任选一个记录作为基准(pivot)，一般选R[low]，以此基准将当前待排区分为左、右两个子区间R[low...pivot-1]、R[pivot+1...high],并使左子区间中所有记录均小于或等于基准记录，右子区间中所有均大于或等于基准记录，而基准记录位于准确的位置上，它无需参加后续的排序。
(2)求解
分别对左右子区间进行快速排序。
(3)组合
由于分治一般最后需要把递归处理的子区间组合起来，但是快速排序之后左右子区间均有序，组合并不需要进行其他操作。
Java代码：
//快速排序
public static void quickSort(int[] source,int low,int high){
if(low<high){
int piv = partition(source,low,high);
System.out.println("piv:"+source[piv]);
quickSort(source,low,piv-1);
quickSort(source,piv+1,high);
}
}
private static int partition(int[] source, int i, int j) {
int temp = source[i];
while(i<j){
while(i<j&&source[j]>=temp){
j--;
}
if(i<j)
source[i++] = source[j];
while(i<j&&source[i]<=temp){
i++;
}
if(i<j)
source[j--] = source[i];
}
source[i] = temp;
return i;
}
平均O(nlog n)，最坏情况O(n^2).
划分算法Partition
1.设置2个指针i和j，初值分别为low和high，选取待排区第一个记录source[i]作为基准pivot。
2.令j自high起向左扫描，直到找到第一个小于pivot的记录source[j],将source[j]赋值给source[i]，再令i自i+1起向右扫描，直到找到第一个大于pivot的记录source[i]，将source[i]赋值给source[j],再令j自j-1向左扫描，如此交替反复，直到i=j为止，i便是pivot最终的位置，这就完成了一次划分。
划分过程.jpg
排序全过程.jpg
快速排序也是不稳定的。
基数排序
基本思想：
设置r个队列（r为进制数，例如十进制r=10），队列编号分别为0，1，2，… ，r-1；首先按数据元素关键字最低位上的数字值依次把n个数据元素分配到r个队列中（入队）；
然后按照队列编号从小到大的顺序，将队列中的数据元素收集起来，形成一个新的数据元素序列，这就是第一趟排序。
接着对第一趟基数排序后得到的数据元素序列，再按照数据元素关键字的次低位上的数字值依次把各个数据元素再次分配到r个队列中，然后按照队列编号从小到大的顺序，将队列中的数据元素收集起来。
如此反复，经过m（m为数据元素的最大位数，例如1234，m=4）趟基数排序后，就得到了数据元素的有序序列。
需注意的是，对同一个队列中的数据元素，在收集过程中，应按照先进入队列的先收集，后进入队列的后收集的规则进行。
//基数排序(根据关键字依次排序)
public static void main(String[] args){
int[] source = new int[]{211,987,237,568,346,875,453};
baseNumSort(source,3,10);
}
private static void baseNumSort(int[] source, int digit, int r) {
//如十进制就定义十个队列
Queue[] que = new Queue[r];
for(int i = 0;i<r;i++){
que[i] = new LinkedList<Integer>();
}
for(int i = 0;i<digit;i++){
for(int j = 0;j<source.length;j++){
int k = getDigitNum(source[j],i,r);//取出source[j]中的第i位数
que[k].offer(source[j]);
}
int m = 0;
for(int n = 0;n<r;n++){
//将队列的数据全部出列放入原来的数组中
while(!que[n].isEmpty()){
source[m++]= (int)que[n].remove();
}
}
//输出每趟排序后的结果
for(int k = 0;k<source.length;k++){
System.out.printf(" "+source[k]);
}
System.out.println();
}
}
private static int getDigitNum(int num, int digit, int r) {
if(digit==0)return num%r;
int temp = num;
for(int i = 0;i<digit+1;i++){
temp = temp/r;
}
return temp%r;
}
各种排序算法复杂度以及稳定性比较：
各算法复杂度稳定性比较
