测试代码：
public class Main { public static void main(String[] args) { //int[] a = {1}; //测试用例1 //int[] a = {}; //测试用例2 //int[] a = {1,2,3,4,5,6,7,8}; //测试用例3 int[] a = {8,7,6,5,4,3,2,1}; //测试用例4 //int[] a = {100,-2,556,89,0,4,-1,3}; //测试用例5 //Main.bubbleSort(a); //测试完成 //Main.seleSort(a); //测试完成 //Main.insertSort(a); //测试完成 //Main.binaryInsertSort(a); //测试完成 //Main.xier(a); //测试完成 }}
一、时间复杂度为O(n^2)的排序算法
**1. 冒泡排序**
1）时间空间复杂度
最好情况下：正序有序，则只需要比较n次。故，为O(n) 最坏情况下: 逆序有序，则需要比较(n-1)+(n-2)+……+1，故，为O(N*N)
2）稳定性
稳定的。
3）代码实现
/** * 冒泡排序 * @param a */private static void bubbleSort(int a[]){ int i,j,t; int len = a.length; for (i = 0; i < len; i++){ for (j = 0; j < (len - i - 1); j++) { if (a[j] > a[j + 1]) { t = a[j]; a[j] = a[j + 1]; a[j + 1] = t; } } } for(i=0;i **2.选择排序**
1）时间空间复杂度
时间复杂度为O(n*n)。
2）稳定性
不稳定的。
比如：2 # 2 # 2 # 1，当选择最小的1到最前面，第一个2换到最后，破坏了稳定性。
3）代码实现
/** * 选择排序 * @param a */private static void seleSort(int a[]){ int i,j,t,k; int len = a.length; for(i=0;i a[k]) j=k; } if(j!=i){ t=a[j]; a[j]=a[i]; a[i]=t; } } for(i=0;i -----------------------------------------------------------
**3.直接插入排序**
1）时间空间复杂度
从空间来看，只需要一个记录的辅助空间；
从时间来看：最好情况（正序有序，只需要比较n次，不需要移动为O(n)）;
最坏情况（逆序有序，每个都需要移动，为O(n*n)）。
2）稳定性
稳定的。（排序前后两个相同的数字前后顺序没有发生变化）
3）代码实现
/** * 直接插入排序 * @param a */private static void insertSort(int[] a){ int i,j,t; int len = a.length; for(i=1;i =0&&t --------------------------------------------------
**4.折半插入排序**
1）时间空间复杂度
折半插入排序与直接插入排序所需额外空间相同，但是移动次数仅比直接插入排序少了关键字的移动次数，因此时间复杂度为O(n*n)。
2）稳定性
稳定的。
3）特点
由折半查找来实现，由此进行的排序称为折半插入排序。
4）代码实现
/** * 折半插入排序 * @param a */private static void binaryInsertSort(int[] a){ int i,j,t; int low,high,m; int len = a.length; for(i=1;i high;--j) a[j+1]=a[j]; //将数据插入 a[high+1]=t; } for(i=0;i
**5快速排序.**
一次快速排序过程
01.随机选择一个值作为划分值，然后与最后一个值交换。
02.设置一个小于等于区间，初始长度为0，放在最开始
03.从左往右遍历所有的值，如果大于划分值，则继续遍历
04.如果遍历到小于等于划分值，则此值与小于等于区间后的第一个值交换，小于等于区间向后移动一个位置。
05.当遍历到最后一个的时候，划分值与小于等于区间后的第一个值交换，完成第一次遍历
06.第一次排序完成后，划分值之前的部分和之后的部分再进行快速排序。
1）时间空间复杂度
最好的情况下：因为每次都将序列分为两个部分(一般二分都复杂度都和logN相关)，故为 O(N*logN) 最坏的情况下：基本有序时，退化为冒泡排序，几乎要比较N*N次，故为O(N*N)
2）稳定性
不稳定的。
比如：4 # 3 # 3 # 3 # 1，假如取第二个3作为划分值，则它左右两个三要么全部划分到它的左边，要么划分到它的右边，这样一来就破坏了稳定性。
3）特点
它是由冒泡排序改进而来的。在待排序的n个记录中任取一个记录(通常取第一个记录),把该记录放入适当位置后,数据序列被此记录划分成两部分。所有关键字比该记录关键字小的记录放置在前一部分,所有比它大的记录放置在后一部分,并把该记录排在这两部分的中间(称为该记录归位),这个过程称作一趟快速排序。
4）代码实现
public class Main { public static void main(String[] args) { int[] a = {1}; //测试用例1 //int[] a = {}; //测试用例2 //int[] a = {1,2,3,4,5,6,7,8}; //测试用例3 //int[] a = {8,7,6,5,4,3,2,1}; //测试用例4 //int[] a = {100,-2,556,89,0,4,-1,3}; //测试用例5 int p = 0,r = a.length - 1; Main.QuickSort(a, p, r); for(int i=0;i<=r;i++) System.out.println(a[i]); } /** * 快速排序 * @param a * @param p * @param r */ private static void QuickSort(int[] a,int p,int r){ int q; if(p **6.希尔排序**
具体过程
01.假如初始步长设为3，前三个数字是不考虑的。
02.从1开始，往前跳三位与6比较，小于，进行交换；1再往前跳三位数组越界，停止交换，指针指向下一个数字8，进行调整。
03.8往前跳三位为5，大于，停止交换过程，进行下一个数字的调整。下一个为7，7往前跳三位，大于3，停止交换过程，进行下一个数字的调整。
04.指针现在指向2，向前跳三位，小于6，交换；2再向前跳三位，大于1，停止交换过程，进行下一个数字的调整。
05.指针现在指向4，4向前跳三位小于8，交换；4再向前跳三位小于5，交换；4再向前跳三位，数组越界，停止交换。4往下没有数字了，所以步长为3的步骤结束。
06.希尔排序最终结束的步长为1，也就是经典的插入排序。希尔排序的关键是步长的选择，步长决定希尔排序的性能。
1）时间空间复杂度
由于所取"增量"的问题，最好的时间复杂度尚未得出。
最坏的跟平均时间复杂度为：O(N*logN)
2）稳定性
不稳定。
比如：5 # 1 # 1 # 5，当步长为2，则第二个1向前跳两位，与5交换： 1 # 1 # 5 # 5，破环了稳定性。
3）特点
希尔排序可以说是一种分组插入排序。
希尔排序分析是一个复杂的问题，因为它的时间是所取“增量”序列的函数，这也涉及到一些数学方面尚未解决的难题。但是应该注意：应使增量序列中的值没有除1之外的公因子，并且最后一个增量值必须等于1。
4）代码实现
/** * 希尔排序 * @param a */private static void xier(int a[]) { int size = a.length; int i, j, k, temp; for (i = size / 2; i > 0; i /= 2) { for (j = i; j < size; j++) { temp = a[j]; for (k = j - i; k >= 0 && temp < a[k]; k -= i) { a[k + i] = a[k]; } a[k + i] = temp; } } for(i=0;i -------------------------------------------------------------
**7.归并排序**
1）时间空间复杂度
对长度为n的文件，需进行logN 趟二路归并，每趟归并的时间为O(n)，故其时间复杂度无论是在最好情况下还是在最坏情况下均是O(nlgn)。
2）稳定性
稳定。
3）特点
缺点是需要O(n)的额外空间，适合多链表排序。
4）代码实现
public class Main { public static void main(String[] args) { int[] a = {1}; //测试用例1 //int[] a = {}; //测试用例2 //int[] a = {1,2,3,4,5,6,7,8}; //测试用例3 //int[] a = {8,7,6,5,4,3,2,1}; //测试用例4 //int[] a = {100,-2,556,89,0,4,-1,3}; //测试用例5 int low = 0,high = a.length - 1; Main.MergeSort(a, low, high); for(int i=0;i
-------------------------------------------------
**8.堆排序**
01.构建一个大小为n的大根堆
02.将堆顶元素与堆的最后一个数交换，然后将堆中最后一个数移出堆结构，放在数组的最后位置，作为数组的有序部分保存下来。
03.然后将n-1大小的堆进行大根堆的调整，还是将堆顶位置元素与堆的最后位置元素交换，堆数量减一；将最大值放在数组最后也是，作为数组的有序部分。
04.依次进行上述操作，当堆的大小减为1的时候整个数组就有序了。
1）时间空间复杂度
O(N*logN)
2）稳定性
不稳定。
3）特点
利用完全二叉树中双亲节点和孩子节点之间的内在关系，在当前无序区中选择关键字最大(或者最小)的记录。也就是说，以最小堆为例，根节点为最小元素，较大的节点偏向于分布在堆底附近。
4）代码实现
void HeapAdjust(int *a,int i,int size) //调整堆 { int lchild=2*i; //左孩子节点序号 int rchild=2*i+1; //右孩子节点序号 int max=i; //临时变量 if(i<=size/2) //如果i不是叶节点就不用进行调整 { if(lchild<=size&&a[lchild]>a[max]) { max=lchild; } if(rchild<=size&&a[rchild]>a[max]) { max=rchild; } if(max!=i) { swap(a[i],a[max]); HeapAdjust(a,max,size); //避免调整之后以max为父节点的子树不是堆 } } }void BuildHeap(int *a,int size) //建立堆 { int i; for(i=size/2;i>=1;i--) //非叶节点最大序号值为size/2 { HeapAdjust(a,i,size); } } void HeapSort(int *a,int size) //堆排序 { int i; BuildHeap(a,size); for(i=size;i>=1;i--) { swap(a[1],a[i]); //交换堆顶和最后一个元素，即每次将剩余元素中的最大者放到最后面 //将余下元素重新建立为大顶堆 HeapAdjust(a,1,i-1); //重新调整堆顶节点成为大顶堆 }} int main(int argc, char *argv[]){ int a[100]; int size; while(scanf("%d",&size)==1&&size>0) { int i; for(i=1;i<=size;i++) cin>>a[i]; HeapSort(a,size); for(i=1;i<=size;i++) cout< <<" "; cout<
时间复杂度为O(N)的排序算法
不是基于比较的算法，思想来自桶排序，经典的就是基数排序和计数排序。
**9.基数排序**
01.假设一串十进制数，有0-9号桶。
02.第一步根据个位数数值进桶。
03.然后从0号桶到9号桶依次到处数据，形成一个次序。然后再根据十位上的数值依次进桶，然后倒出；最终根据最高位上数值进桶 倒出后形成的次序就是一个有序次序。
**10.计数排序**
比如：对员工的身高进行排序，成年人的身高在一米到三米之间。
例：对公司所有员工按照年龄排序，可以有O(n)的辅助内存。
说明要排序的数在一个较小的范围内。
void SortAges(int ages[],int length){ if(age==NULL||length<=0) return; const int oldestAge=99; int timesOfAge[oldestAge+1]; for(int i=0;i<=oldestAge;++i) timesOfAge[i]=0; for(int i=0;i <0||age>oldestAge) throw new std::exception("age out of range."); ++timesOfAge[age]; } int index=0; for(int i=0;i<=oldestAge;++i){ for(int j=0;j 各个排序算法使用的时间复杂度总结：
时间复杂度为O(N)的排序算法
不是基于比较的算法，思想来自桶排序，经典的就是基数排序和计数排序。
各个排序算法使用的空间复杂度总结：
各个排序算法稳定性总结：
补充说明一：排序算法无绝对优劣
通常不能随便说哪种排序算法好。这个和要排序的元素相关。例如对人的年龄排序或者身高排序，因为这种数据范围通常比较小，可以考虑采用计数排序。但是对于均匀分布的整数，计数排序就不合适了。一般情况下没有特殊说明的话，认为要排序的数据范围是均匀分布的。
补充说明二：为什么叫快速排序
快速排序之所以叫快速排序，并不代表它比堆排序和归并排序优良。在最好的情况下，它的渐进复杂度与堆排序和归并排序是相同的。只是快速排序的常量系数比较小而已。
补充说明三：工程上的排序
1、工程上的排序是综合排序。
2、数组较小时，插入排序。
3、数组较大时、快速排序或其他O(N*logN)的排序。
各种排序比较：