排序問題
<!--more-->
排序方法? ? ? ? 平均情況? ? ? ? 最好情況? ? ? ? 最壞情況? ? ? ? 輔助空間? ? ? ? 穩(wěn)定性
冒泡排序? ? ? ? O(n^2)? ? ? ? ? O(n)? ? ? ? ? ? ? O(n^2)? ? ? ? ? ? O(1)? ? ? ? ? ? ? ? 穩(wěn)定
選擇排序? ? ? ? O(n^2)? ? ? ? ? O(n^2)? ? ? ? ? ? O(n^2)? ? ? ? ? ? O(1)? ? ? ? ? ? ? 不穩(wěn)定
插入排序? ? ? ? O(n^2)? ? ? ? ? O(n)? ? ? ? ? ? ? O(n^2)? ? ? ? ? ? O(1)? ? ? ? ? ? ? ? 穩(wěn)定
希爾排序O(n*log(n))~O(n^2) O(n^1.3)? ? ? O(n^2)? ? ? ? ? ? O(1)? ? ? ? ? ? ? 不穩(wěn)定
堆排序? ? ? ? ? O(nlog(n))? ? O(nlog(n))? ? O(n*log(n))? ? ? O(1)? ? ? ? ? ? ? 不穩(wěn)定
歸并排序? ? ? O(nlog(n))? ? O(nlog(n))? ? O(n*log(n))? ? ? O(n)? ? ? ? ? ? ? ? 穩(wěn)定
快速排序? ? ? O(nlog(n))? ? O(nlog(n))? ? ? O(n^2)? ? ? ? ? ? O(1)? ? ? ? ? ? ? 不穩(wěn)定
關于穩(wěn)定性： 假定在待排序的記錄序列中嘁圈，存在多個具有相同的關鍵字的記錄摩泪，若經(jīng)過排序，這些記錄的相對次序保持不變直撤，即在原序列中，ri=rj耕皮，且ri在rj之前境蜕，而在排序后的序列中，ri仍在rj之前凌停，則稱這種排序算法是穩(wěn)定的;否則稱為不穩(wěn)定的粱年。
（一）冒泡排序
基本思想 ：在一組沒有排序的數(shù)組中，通過自上而下對相鄰的兩個數(shù)進行比較罚拟，讓較大的數(shù)下沉
即：每當兩相鄰的數(shù)比較后發(fā)現(xiàn)它們的排序與排序要求相反時台诗，就將它們互換
時間復雜度 ：無論給定什么數(shù)列，都需要比較 n（n-1）,則為 O(n^2)
// 冒泡排序赐俗，返回升序數(shù)組
? ? publicstaticvoidbubbleSort(inta[],intn) {
? ? ? ? for(inti=0;i<n-1;i++) {
? ? ? ? ? ? for(intj=0;j<n-1-i;j++)
? ? ? ? ? ? ? ? if(a[j]>a[j+1]) {
? ? ? ? ? ? ? ? ? ? inttmp=a[j];
? ? ? ? ? ? ? ? ? ? a[j]=a[j+1];
? ? ? ? ? ? ? ? ? ? a[j+1]=tmp;
? ? ? ? ? ? }
? ? ? ? }
? ? }
改進的冒泡排序 ：
改進后拉队，當傳入的數(shù)組為已經(jīng)排序的的時，只需進行 n 次比較阻逮，則為? O(n)粱快，為最優(yōu)情況
對冒泡排序常見的改進方法是加入一標志性變量flag，用于標志某一趟排序過程中是否有數(shù)據(jù)交換叔扼，如果進行某一趟排序時并沒有進行數(shù)據(jù)交換事哭，則說明數(shù)據(jù)已經(jīng)按要求排列好，可立即結束排序瓜富，避免不必要的比較過程
// 冒泡排序鳍咱，返回升序數(shù)組
? ? publicstaticvoidbubbleSort_1(inta[],intn) {
? ? ? ? booleanflag;
? ? ? ? for(inti=0;i<n-1;i++) {
? ? ? ? ? ? flag=false;
? ? ? ? ? ? for(intj=0;j<n-1-i;j++)
? ? ? ? ? ? ? ? if(a[j]>a[j+1]) {
? ? ? ? ? ? ? ? ? ? inttmp=a[j];
? ? ? ? ? ? ? ? ? ? a[j]=a[j+1];
? ? ? ? ? ? ? ? ? ? a[j+1]=tmp;
? ? ? ? ? ? ? ? ? ? flag=true;
? ? ? ? ? ? ? ? }
? ? ? ? ? ? if(flag==false)
? ? ? ? ? ? ? ? break;
? ? ? ? }
? ? }
對于每次的排序，記錄下交換的位置pos,則當一次排序結束后与柑，可以得到最后一次排序的坐標谤辜，當下一趟排序開始時，只需要比較到pos 就可以了价捧，因為pos 后面的都已經(jīng)排序好了丑念。
publicstaticvoidbubbleSort_2(intr[],intn) {
? ? inti=n-1;// 初始時,最后位置保持不變
? ? while(i>0) {
? ? ? ? intpos=0;// 每趟開始時,無記錄交換
? ? ? ? for(intj=0;j<i;j++)
? ? ? ? ? ? if(r[j]>r[j+1]) {
? ? ? ? ? ? ? ? pos=j;// 記錄交換的位置
? ? ? ? ? ? ? ? inttmp=r[j];
? ? ? ? ? ? ? ? r[j]=r[j+1];
? ? ? ? ? ? ? ? r[j+1]=tmp;
? ? ? ? ? ? }
? ? ? ? i=pos;// 為下一趟排序作準備
? ? }
}
（二）選擇排序
算法思想 ：在第一次排序，掃描N個數(shù)據(jù)结蟋，選出其中的最小值脯倚，與第一個元素交換，接著進行第二趟椎眯，以此類推
復雜度 ： 平均時間復雜度：O(n2)挠将。當有重復元素時胳岂，會改變位置编整，比如【2,2,5】，第一趟第1,2就會交換位置乳丰，所以此算法為不穩(wěn)定的掌测。
? ? // 選擇排序
? ? staticvoidselectionSort(inta[],intn) {
? ? ? ? intindex;
? ? ? ? for(inti=0;i<n;i++) {
? ? ? ? ? ? index=i;
? ? ? ? ? ? for(intj=i+1;j<n-1;j++) {
? ? ? ? ? ? ? ? if(a[j]<a[index])
? ? ? ? ? ? ? ? ? ? index=j;
? ? ? ? ? ? ? ? if(index!=i) {
? ? ? ? ? ? ? ? ? ? inttmp=a[index];
? ? ? ? ? ? ? ? ? ? a[index]=a[i];
? ? ? ? ? ? ? ? ? ? a[i]=tmp;
? ? ? ? ? ? ? ? }
? ? ? ? ? ? }
? ? ? ? }
? ? }
(三) 插入排序
算法思想 ：把數(shù)據(jù)分成有序組和插入組，一般把第一個元素當成有序組，然后從插入組中拿第一個數(shù)據(jù)汞斧，從有序組的最后一個元素進行比較夜郁，找到合適的位置并插入，為穩(wěn)定排序粘勒。
時間復雜度 ：當給定的數(shù)據(jù)為排序升序時竞端，只要比較N 次，為O(n)庙睡；當是降序時事富，要 n(n+1)/2，所以為O(n^2)
平均的時間復雜度為O(n^2)乘陪。
//插入排序
? ? publicstaticvoidInsertionSort(inta[],intn)
? ? {
? ? inti=0;
? ? intj=0;
? ? inttmp=0;
? ? for(i=1;i<n;i++)
? ? {
? ? tmp=a[i];//從待插入組取出第一個元素统台。 ?
? ? j=i-1;//i-1即為有序組最后一個元素（與待插入元素相鄰）的下標 ?
? ? while(j>=0&&tmp<a[j])//注意判斷條件為兩個，j>=0對其進行邊界限制啡邑。第二個為插入判斷條件 ?
? ? {
? ? a[j+1]=a[j];//若不是合適位置贱勃，有序組元素向后移動 ?
? ? j--;
? ? }
? ? a[j+1]=tmp;//找到合適位置，將元素插入谤逼。 ?
? ? }
? ? }
（四）希爾排序
算法思想 : 將無序數(shù)組分割為若干個子 序列贵扰，子序列不是逐段分割的，而是相隔特定的增量的子序列森缠，對各個子序列進行插入排序拔鹰；然后再選擇一個更小的增量，再將數(shù)組分割為多個子序列進行排序......最后選擇增量為1贵涵，即使用直接插入排序列肢，使最終數(shù)組成為有序。
時間復雜度 ：O(n*log(n))~O(n^2) ，最壞情況為O(n^2)
? ? // 希爾排序
? ? publicstaticvoidshell_sort(intarr[],intsize) {
? ? ? ? if(arr==null)
? ? ? ? ? ? return;
? ? ? ? inth=1;/* 關于步長哆窿，取值沒有統(tǒng)一標準囚聚，必須小于size，最后一次步長要為1 */
?
? ? ? ? /* 計算首次步長 */
? ? ? ? while(h<size/3)
? ? ? ? ? ? h=3*h+1;
?
? ? ? ? inti,j,temp;
? ? ? ? while(h>=1) {
? ? ? ? ? ? for(i=h;i<size;++i) {
? ? ? ? ? ? ? ? /* 將a[i]插入到a[i-h]欧聘、a[i-2h]、a[i-3h]...中 */
? ? ? ? ? ? ? ? for(j=i;j>=h&&(arr[j]<arr[j-h]);j-=h) {
? ? ? ? ? ? ? ? ? ? temp=arr[j];
? ? ? ? ? ? ? ? ? ? arr[j]=arr[j-h];
? ? ? ? ? ? ? ? ? ? arr[j-h]=temp;
? ? ? ? ? ? ? ? }
? ? ? ? ? ? }
? ? ? ? ? ? /* 計算下一輪步長 */
? ? ? ? ? ? h=h/3;
? ? ? ? }
?
? ? }
?
（五）快速排序
快速排序 ：選取一個數(shù)端盆，位置i怀骤，進行排序比較，從j開始焕妙，選擇比選取的數(shù)小的蒋伦，填補到原來的位置，則此時j位置焚鹊，空出來痕届，再從i++開始，選擇比i大的數(shù)，填補到j的位置研叫，重復排序,則是大的放右邊锤窑，小的左邊，然后繼續(xù)遞歸調動嚷炉。
時間復雜度 ：O(N*logN)
//快速排序
voidquick_sort(ints[],intl,intr)
{
if(l<r)
?? {
inti=l,j=r,x=s[l];
while(i<j)
? ? ?? {
while(i<j&&s[j]>=x)// 從右向左找第一個小于x的數(shù)
? ? ? ? ? ? ? ? j--;
if(i<j)
? ? ? ? ? ? ? ? s[i++]=s[j];
while(i<j&&s[i]<x)// 從左向右找第一個大于等于x的數(shù)
? ? ? ? ? ? ? ? i++;
if(i<j)
? ? ? ? ? ? ? ? s[j--]=s[i];
? ? ?? }
s[i]=x;
quick_sort(s,l,i-1);// 遞歸調用
quick_sort(s,i+1,r);
?? }
}
