實現以下排序
插入排序O(n^2)
冒泡排序 O(n^2)
選擇排序 O(n^2)
快速排序 O(n log n)
堆排序 O(n log n)
歸并排序 O(n log n)
希爾排序 O(n^1.25)
1.插入排序 O(n^2)
一般來說，插入排序都采用in-place在數組上實現。具體算法描述如下：
⒈ 從第一個元素開始，該元素可以認為已經被排序
⒉ 取出下一個元素，在已經排序的元素序列中從后向前掃描
⒊ 如果該元素（已排序）大于新元素，將該元素移到下一位置
⒋ 重復步驟3，直到找到已排序的元素小于或者等于新元素的位置
⒌ 將新元素插入到下一位置中
⒍ 重復步驟2~5
如果比較操作的代價比交換操作大的話，可以采用二分查找法來減少比較操作的數目。該算法可以認為是插入排序的一個變種，稱為二分查找排序。
void insert_sort(int* array,unsignedint n){
int i,j;
int temp;
for(i=1;i<n;i++){
temp=*(array+i);
for(j=i;j>0&&*(array+j-1)>temp;j--){
*(array+j)=*(array+j-1);
}
*(array+j)=temp;
}
}
2.冒泡排序 O(n^2)
冒泡排序算法的運作如下：
比較相鄰的元素。如果第一個比第二個大，就交換他們兩個。
對每一對相鄰元素作同樣的工作，從開始第一對到結尾的最后一對。在這一點，最后的元素應該會是最大的數。
針對所有的元素重復以上的步驟，除了最后一個。
持續每次對越來越少的元素重復上面的步驟，直到沒有任何一對數字需要比較。
#include<stdio.h>
#defineSIZE8
void bublle_sort(int a[],int n){//n為數組a的元素個數
int i,j,temp;
for(j=0;j<n-1;j++)
for(i=0;i<n-1-j;i++)
if(a[i]>a[i+1]){//數組元素大小按升序排列
temp=a[i];
a[i]=a[i+1];
a[i+1]=temp;
}
}
int main(){
int number[SIZE]={95,45,15,78,84,51,24,12};
int i;
bublle_sort(number,SIZE);
for(i=0;i<SIZE;i++){
printf("%d",number[i]);
}
printf("\n");
}
3.選擇排序 O(n^2)
void select_sort(int * a, int n){
register int i, j, min, t;
for( i =0; i < n -1; i ++) {
min = i; //查找最小值
for( j = i +1; j < n; j ++)
if( a[min] > a[j])
min = j; //交換
if(min != i) {
t = a[min];
a[min] = a[i];
a[i] = t;
}
}
}
4.快速排序 O(n log n)
void QuickSort(int a[],int numsize){//a是整形數組，numsize是元素個數
int i=0,j=numsize-1;
int val=a[0];//指定參考值val大小
if(numsize>1){//確保數組長度至少為2，否則無需排序
while(i<j{//循環結束條件
for(;j>i;j--)//從后向前搜索比val小的元素，找到后填到a[i]中并跳出循環
if(a[j]<val){
a[i]=a[j];break;
}
for(;i<j;i++)//從前往后搜索比val大的元素，找到后填到a[j]中并跳出循環
if(a[i]>val){
a[j]=a[i];break;
}
}
a[i]=val;//將保存在val中的數放到a[i]中
QuickSort(a,i);//遞歸，對前i個數排序
QuickSort(a+i+1,numsize-1-i);//對i+1到numsize這numsize-1-i個數排序
}
}
5. 堆排序 O(n log n)
n個關鍵字序列Kl，K2，…，Kn稱為（Heap），當且僅當該序列滿足如下性質（簡稱為堆性質）：
(1)ki<=k(2i）且ki<=k(2i+1)(1≤i≤ n），當然，這是小根堆，大根堆則換成>=號。//k(i）相當于二叉樹的非葉子結點，K(2i）則是左子節點，k(2i+1）是右子節點.
若將此序列所存儲的向量R[1..n]看做是一棵完全二叉樹的存儲結構，則堆實質上是滿足如下性質的完全二叉樹:樹中任一非葉子結點的關鍵字均不大于（或不小于）其左右孩子（若存在）結點的關鍵字。
// array是待調整的堆數組，i是待調整的數組元素的位置，nlength是數組的長度
//本函數功能是：根據數組array構建大根堆
void HeapAdjust(int array[], int i, int nLength)
{
int nChild;
int nTemp;
for (nTemp = array[i]; 2 * i + 1 < nLength; i = nChild)
{
// 子結點的位置=2*（父結點位置）+ 1
nChild = 2 * i + 1;
// 得到子結點中較大的結點
if ( nChild < nLength-1 && array[nChild + 1] > array[nChild])
++nChild;
// 如果較大的子結點大于父結點那么把較大的子結點往上移動，替換它的父結點
if (nTemp < array[nChild])
{
array[i] = array[nChild];
array[nChild]= nTemp;
}
else
// 否則退出循環
break;
}
}
// 堆排序算法
void HeapSort(int array[],int length)
{
int tmp;
// 調整序列的前半部分元素，調整完之后第一個元素是序列的最大的元素
//length/2-1是第一個非葉節點，此處"/"為整除
for (int i = floor(length -1)/ 2 ; i >= 0; --i)
HeapAdjust(array, i, length);
// 從最后一個元素開始對序列進行調整，不斷的縮小調整的范圍直到第一個元素
for (int i = length - 1; i > 0; --i)
{
// 把第一個元素和當前的最后一個元素交換，
// 保證當前的最后一個位置的元素都是在現在的這個序列之中最大的
/// Swap(&array[0], &array[i]);
tmp = array[i];
array[i] = array[0];
array[0] = tmp;
// 不斷縮小調整heap的范圍，每一次調整完畢保證第一個元素是當前序列的最大值
HeapAdjust(array, 0, i);
}
}
6.歸并排序 O(n log n)
將已有序的子序列合并，得到完全有序的序列；即先使每個子序列有序，再使子序列段間有序。若將兩個 有序表合并成一個有序表，稱為二路歸并。
//歸并操作
void Merge(int sourceArr[], int targetArr[], int startIndex, int midIndex, int endIndex)
{
int i, j, k;
for(i = midIndex+1, j = startIndex; startIndex <= midIndex && i <= endIndex; j++)
{
if(sourceArr[startIndex] < sourceArr[i])
{
targetArr[j] = sourceArr[startIndex++];
}
else
{
targetArr[j] = sourceArr[i++];
}
}
if(startIndex <= midIndex)
{
for(k = 0; k <= midIndex-startIndex; k++)
{
targetArr[j+k] = sourceArr[startIndex+k];
}
}
if(i <= endIndex)
{
for(k = 0; k <= endIndex- i; k++)
{
targetArr[j+k] = sourceArr[i+k];
}
}
}
//內部使用遞歸，空間復雜度為n+logn
void MergeSort(int sourceArr[], int targetArr[], int startIndex, int endIndex)
{
int midIndex;
int tempArr[100]; //此處大小依需求更改
if(startIndex == endIndex)
{
targetArr[startIndex] = sourceArr[startIndex];
}
else
{
midIndex = (startIndex + endIndex)/2;
MergeSort(sourceArr, tempArr, startIndex, midIndex);
MergeSort(sourceArr, tempArr, midIndex+1, endIndex);
Merge(tempArr, targetArr,startIndex, midIndex, endIndex);
}
}
//調用
int _tmain(int argc, _TCHAR* argv[])
{
int a[8]={50,10,20,30,70,40,80,60};
int b[8];
MergeSort(a, b, 0, 7);
for(int i = 0; i < sizeof(a) / sizeof(*a); i++)
cout << b[i] << ' ';
cout << endl;
system("pause");
return 0;
}
7.希爾排序 O(n^1.25）
先取一個小于n的整數d1作為第一個增量，把文件的全部記錄分成d1個組。所有距離為d1的倍數的記錄放在同一個組中。先在各組內進行直接插入排序；然后，取第二個增量d2<d1重復上述的分組和排序，直至所取的增量dt=1(dt<dt-l<…<d2<d1)，即所有記錄放在同一組中進行直接插入排序為止。
void ShellSort(int a[], int n){
int d, i, j, temp;
for(d = n/2;d >= 1;d = d/2){
for(i = d; i < n;i++){
temp = a[i];
for(j = i - d;(j >= 0) && (a[j] > temp);j = j-d){
a[j + d] = a[j];
}
a[j + d] = temp;
}
}
}
