稳定排序与不稳定排序
- 稳定排序：两个相等的数在排序前和排序后的位置不发生改变。
冒泡排序、插入排序、归并排序、基数排序 - 不稳定排序：选择排序、快速排序、希尔排序、堆排序
插入排序（Insert Sort）
基本思想
遍历数组，确保之前遍历过的元素已排序；每遍历到一个数，寻找这个数在之前遍历过的已排序数中的位置，并且通过不断移位进行插入，该算法的时间复杂度为O(n^2)，空间复杂度为O(1)。
java程序：
public void insertSort(int[] a) {//升序排序
int n=a.length;
for(int i=1;i<n;i++){
int key=a[i];
int j=i-1;
while(j>=0&&a[j]>key){
a[j+1]=a[j];
j--;
}
a[j+1]=key;
}
}
冒泡排序（Bubble Sort）
基本思想
以升序排序为例，从下往上冒泡是指从数组最后一个元素开始相邻的元素进行比较，如果大的元素在小的元素前面两者就进行交换，这样最小的元素就会通过不断交换到达最前面从而完成排序。
java程序
public void bubbleSort(int[] a) {
boolean noswap; //定义未交换标志
for(int i=0;i<a.length;i++){
noswap=true;//每一轮交换开始设置未交换标志为真
for(int j=a.length-1;j>i;j--){
if(a[j]<a[j-1]){
swap(a,j-1,j);
noswap=false;
}
}
if(noswap) break;//如果一轮都没有交换则终止算法
}
}
public void swap(int[] a, int i, int j) {
int temp=a[i];
a[i]=a[j];
a[j]=temp;
}
归并排序（Merge Sort）
基本思想
分治思想（divide & conquer）:将数组分成两半分别进行排序，然后将两个已经排序好的数组合并起来，形成一个已经排序完成的数组。该算法的重点是合并函数，两个已经排序好的数组进行排序即通过比较两个数组现指针所指位置元素的值，取出较小元素，对应指针后移，直到遍历完所有元素，所需时间O(n)。时间复杂度计算：T(n)=2T(n/2)+n，利用递归树进行计算可以得到T(n)=o(nlgn)。
java程序
public static void mergeSort(int[] a,int start,int end) {
if(start<end){
int mid=(start+end)/2;
mergeSort(a,start,mid);
mergeSort(a,mid+1,end);
merge(a,start,mid,end);
}
}
public static void merge(int[] a, int start,int mid,int end) {
int[] arr1=Arrays.copyOfRange(a, start, mid+1);
int[] arr2=Arrays.copyOfRange(a,mid+1, end+1);
int p1=0;
int p2=0;
for(int i=0;i<end-start+1;i++){
if(p1<arr1.length&&p2<arr2.length){
if(arr1[p1]<arr2[p2]){
a[i+start]=arr1[p1];
p1++;
}
else{
a[i+start]=arr2[p2];
p2++;
}
}
else if(p1==arr1.length&&p2<arr2.length){
a[i+start]=arr2[p2];
p2++;
}
else if(p2==arr2.length&&p1<arr1.length){
a[i+start]=arr1[p1];
p1++;
}
else break;
}
}
快速排序（Quick Sort）
基本思想
分治思想：首先在数组中选取一个元素作为主元（pivot），将原数组重新组合即前面部分是比主元小的元素然后是主元然后是比主元大的部分，此时主元处于排序后的正确位置，然后递归快速排序，将主元前部分和主元后部分分别快速排序，知道所有都处在正确位置为止。注意主元的选取最后为随机的，那么其平均时间复杂度为O(nlgn)。
举个例子
2,4,3,1,8,5
开始将2作为主元：
4与2比较，比2大位置不变，此时不大于2的元素个数为0：2,4,3,1,8,5；
3与2比较，比2大位置不变，此时不大于2的元素个数为0：2,4,3,1,8,5；
3与2比较，比2小位置改变，此时不大于2的元素个数为1：2,1,3,4,8,5；
.....
经过一轮遍历后不大于2的元素个数为1，因此将1号位的元素与2交换：1,2,3,4,8,5；
接着排序：1（不用排）和3,4,8,5-->3,4,8,5-->3（不用排）和4,8,5-->4（不用排）和8,5-->5,8
java程序
public void quickSort(int[] a, int p, int q) {
if(p<q){
int r=partition(a,p,q);
quickSort(a,p,r-1);
quickSort(a,r+1,q);
}
}
public int partition(int[] a, int p, int q) {
Random r=new Random(); //随机选取主元
int index=r.nextInt(q-p)+p;
int x=a[index];
swap(a,p,index);
int i=p;
for(int j=p+1;j<=q;j++){
if(a[j]<=x){
i=i+1;
swap(a,i,j);
}
}
swap(a,p,i);
return i;
}
public void swap(int[] a, int i, int j) {
int temp=a[i];
a[i]=a[j];
a[j]=temp;
}
堆排序（Heap Sort）
基本思想
最大堆指的是父节点元素大于子节点元素的完全二叉树。构造最大堆：
数组a按照顺序生成一个完全二叉树，则不是叶节点的节点范围为a[0]~a[a.length/2-1]，对于任意不是叶节点的节点a[i]，其左节点为a[2i+1]，右节点为a[2i+2]，将父节点与左右节点进行比较交换，使父节点的值大于左右节点。最大堆排序利用最大堆的性质，即其根节点元素为所有元素的最大值，因此每次提取出根节点元素，即将其放到最后位置，然后对其前面的元素重构成最大堆，以此类推最后的数组则是已经排序好的数组（从大到小排序）。该算法时间复杂度为O(lgn)。
举个例子
数组a=[16,4,9,10,14,7,9,3];
开始的完全二叉树为：[16,4,9,10,14,7,9,3]
经过重新构造的最大堆为：[16,14,9,10,4,7,9,3]
二叉堆排序：
降低一个元素（最大值与最后一个元素交换）：[3,14,9,10,4,7,9,16]
经过交换得：[14,10,9,3,4,7,9,16]-->[9,10,9,3,4,7,14,16]-->[10,9,9,3,4,7,14,16]-->[7,9,9,3,4,10,14,16]
-->[9,7,9,3,4,10,14,16]-->[4,7,9,3,9,10,14,16]-->[9,7,4,3,9,10,14,16]-->[3,7,4,9,9,10,14,16]
-->[7,3,4,9,9,10,14,16]-->[4,3,7,9,9,10,14,16]-->[3,4,7,9,9,10,14,16]
java程序
public static void heapSort(int[] a) {
buildMaxHeap(a);
int heapSize=a.length;
for(int i=a.length-1;i>=0;i--){
swap(a,0,i);
heapSize-=1;
maxHeap(a,0,heapSize);
}
}
public static void swap(int[] a, int i, int j) {
int tmp=a[i];
a[i]=a[j];
a[j]=tmp;
}
public static void buildMaxHeap(int[] a) {
int heapSize=a.length;
for(int i=a.length/2-1;i>=0;i--){
maxHeap(a,i,heapSize);
}
}
public static void maxHeap(int[] a, int i,int heapSize) {
int left=2*i+1;
int right=2*i;
int largest=0;
if(left<heapSize&&a[i]<a[left]){
largest=left;
}
else largest=i;
if(right<heapSize&&a[right]>a[largest]){
largest=right;
}
if(largest!=i){
swap(a,i,largest);
maxHeap(a,largest,heapSize);
}
}
计数排序（Count Sort）
基本思想
该排序算法适用于0~k范围内的整数（k不是很大）。计数排序即记录下每个数字出现的频率，并且当前所在下标中存储的是小于等于该下标的元素个数（即当前下标的数值应该在排序后的数组中的位置），然后根据该位置进行排序。该算法的时间复杂度为O(n+k)，空间复杂度为O(n+k)。
java程序
public static int[] countSort(int[] a) {
int k=a[0];
int n=a.length;
for(int i=1;i<n;i++){
if(k<a[i]) k=a[i];
}
int[] c=new int[k+1];
int[] b=new int[n];
for(int i=0;i<n;i++){
c[a[i]]=c[a[i]]+1;
}
for(int i=1;i<=k;i++){
c[i]=c[i]+c[i-1];
}
for(int j=0;j<n;j++){
b[c[a[j]]-1]=a[j];
c[a[j]]-=1;
}
return b;
}
桶排序
基本思想
桶排序利用的是哈希表
public static void bucketSort(double[] arr) {
// TODO Auto-generated method stub
int n=arr.length;
List<Double>[] b=new List[n];
for(int i=0;i<n;i++){
b[i]=new ArrayList<Double>();
}//initial buckets
for(int i=0;i<n;i++){
int j=(int)Math.floor(arr[i]*n);
b[j].add(arr[i]);
}// add elements to buckets
for(int i=0;i<n;i++){
for(int k=1;k<b[i].size();k++){
double key=b[i].get(k);
int j=k-1;
while(j>=0&&b[i].get(j)>key){
b[i].set(j+1, b[i].get(j));
j--;
}
b[i].set(j+1, key);
}
}// sort each bucket
int k=0;
for(int i=0;i<n;i++){
for(int j=0;j<b[i].size();j++){
arr[k]=b[i].get(j);
k=k+1;
}
}
}
