幾種常見的排序方法

/*1.插入排序*/
/*算法思路：
??假設(shè)待排序的n個元素存放在數(shù)組a[n]里面，并且a[0]到a[i-1]是已排好序列的元素，而?a[i]到
??a[n-1]是未排序的元素，把未排序的元素?a[i]插入到a[0]到a[i-1]里面，使得a[0]--a[i]成為有序
??經(jīng)歷i=1到i=?n-1次插入后排序完成
??使用在數(shù)組和鏈表都可以，使用在元素較少的情況下
??
??時間復雜度O（n^2),空間復雜度O（1）
*/
void?insert_sort(int?*a,int?n)
{
????int?i,j,t;
????for(i=1;i=0&&t<a[j];j--)
????????{
????????????a[j+1]=t;
????????}
????}
}
/*2.選擇排序法
算法思路：假定待排序的n個元素在數(shù)組a[n]里面，從序列的后n-i+1（i=0,1,2..n-2)個元素a[i],a[i+1]..a[n]
中?至少?選擇一個最小元素a[k]與前面的元素?a[i]交換位置，這個過程從i=0,直到?i=n-2為止的n-1次選擇交換后
，a[0],a[1]...?a[n-1]就完成了

時間復雜度O（n^2),空間復雜度O（1）

穩(wěn)定性排序不穩(wěn)定，在直接選擇排序中，存在不相鄰的元素之間的互換，可能會改變具有相同的排序碼的元素前后位置
簡單的排序方法，適用于元素個數(shù)較少的情況*/
void?select_sort(int?*a,int?n)
{
????int?i,j,k,t;
????for(i=0;i<n-1;i++)
????{
????????k=i;
????????for(j=i+1;j<n;j++)
????????{
????????????if(a[j]<a[k])
????????????????k=j;
????????}
????????t=a[i];
????????a[i]=a[k];
????????a[k]=t;
????}
}
/*3.冒泡排序
????算法思路：設(shè)待排序的n個元素放在數(shù)組a[n]中，無序區(qū)間的范圍是（a[0],a[1]..a[n-1])
????要求在當前無序區(qū)內(nèi)，從最上面的元素a[0]開始，對每個相鄰的元素a[i+1]和a[i](0,1..n-1)
????進行比較，使值較小的元素換至較大的元素之上，經(jīng)過一趟冒泡，假設(shè)最后下移的元素是a[k],則無序
????區(qū)中值較大的幾個元素到達下端并從小到達依次在a[k+1],a[k+2],a[n-1]里面，無序區(qū)間范圍變成
????a[0],a[1]...a[k]然后在當前的無序區(qū)間進行下一趟排序
????
????復雜度:空間O(n^2),時間O（1）
????
????穩(wěn)定性：穩(wěn)定，值相同的元素不會互換位置
????????
*/
void?bubble_sort(int?*a,int?n)
{
????int?i,j,k;
????for(i=0;i<n;i++)
????{
????????for(j=0;ja[j+1])
????????????{
????????????????k=a[j];
????????????????a[j]=a[j+1];
????????????????a[j+1]=k;
????????????}

????????}
????}
}
void?bubble_sort2(int?*a,int?n)
{
????int?i,k,t;
????n--;
????while(n>0)
????{
????????k=0;
????????for(i=0;ia[i+1])
????????????{
????????????????t=a[i];
????????????????a[i]=a[i+1];
????????????????a[i+1]=t;
????????????????k=i;/*k保存最后交換的位置*/
????????????}
????????}
????????n=k;/*n保存無序區(qū)的最大下標*/
????}
}
/*4.希爾排序*/
/*算法思路：設(shè)待排序的n個元素放在數(shù)組a[n]中，首先選擇一組增量，?d0,d1..dt-1,n>d0>d1>..>dt-1=1
??對于?i=0，1..t-1，依次進行下面的各趟處理根據(jù)當前的增量di將n個元素分成di個組，每組元素的下標相隔
??di,即a[k],a[k+di],a[k+2*di],..(k=0,1...di-1);再對各組元素進行插入排序。
????
??復雜度：O（nlog2n)和O（n^2)之間?空間復雜度O（1）
??穩(wěn)定性：不穩(wěn)定，值相同的元素在某趟排序可能分在不同的組，組內(nèi)元素排序元素會移動，位置會互換
??希爾排序比插入排序復雜
*/
void?shell_sort(int?*a,int?*d,int?t,int?n)//d存放增量，t為增量的個數(shù)
{
????int?i,j,k,y;
????for(i=0;i<t;i++)
????{
????????for(j=d[i];j=0&&y<a[k];k-=d[i])
????????????????a[k+d[i]]=a[k];
????????????a[k+d[i]]=y;
????????}
????}
}
/*快速排序
??算法思路：在待排序的序列里面，任意選擇一個元素，通過某種方法，把該元素放在合適的位置上，使得序列中值小于
??該元素的所有元素都在該元素的左邊，值大于該元素的所有元素都在該元素的右邊，這樣所選擇的元素正好處在它應(yīng)該
??在的排序的最終位置上
????
??復雜度：平均O（nlog2n).最壞O（n^2)
??不穩(wěn)定
*/
void?quick_sort(int?*a,int?s,int?e)//s,e表示排序的開始位置和結(jié)束位置
{
????int?i,j,t;
????if(s<e)
????{
????????i=s;
????????j=e;
????????t=a[s];
????????while(i!=j)
????????{
????????????while(it)
????????????????i++;
????????????if(i<j)
????????????????a[j--]=a[i];
????????}
????????a[i]=t;
????????quick_sort(a,s,i-1);
????????quick_sort(a,i+1,e);
????}
}