問題：數(shù)組排序（即按某種特定的順序排列數(shù)據(jù)，如升序或降序）是最重要的計(jì)算應(yīng)用之一，銀行用帳號(hào)對(duì)所有的支票進(jìn)行能夠排序，并根據(jù)排序結(jié)果準(zhǔn)備月底的財(cái)務(wù)報(bào)告，學(xué)校學(xué)生成績管理系統(tǒng)用數(shù)組排序的方法將考試成績從高到低進(jìn)行排名，數(shù)組排序方法很多，有直接插入排序、冒泡排序、快速排序、直接選擇排序，下面來詳細(xì)介紹這四種基本的排序方法及其實(shí)現(xiàn)。
1，直接插入排序：當(dāng)數(shù)據(jù)表A中每個(gè)元素距其最終位置不遠(yuǎn)，數(shù)據(jù)表A按關(guān)鍵字值基本有序，可用此方法排序較快。
2，冒泡排序法：將較小的值“上浮”到數(shù)組頂部，而較大值“下沉”到數(shù)組底部，這種排序技術(shù)要比較好幾趟，每一趟要比較連續(xù)的數(shù)組元素對(duì)，如果某對(duì)數(shù)值是按升序排序的（或者這兩個(gè)值相等），那就保持原樣，如果某對(duì)數(shù)組是按降序排列的，就要交換它們的值。
3，快速排序法：快速排序是對(duì)冒泡排序的一種改進(jìn)。它的基本思想是：通過一躺排序?qū)⒁判虻臄?shù)據(jù)分割成獨(dú)立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小，然后再按次方法對(duì)這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序，整個(gè)排序過程可以遞歸進(jìn)行，以此達(dá)到整個(gè)數(shù)據(jù)變成有序序列。
4，直接選擇排序法：直接選擇排序的作法是：第一趟掃描所有數(shù)據(jù)，選擇其中最小的一個(gè)與第一個(gè)數(shù)據(jù)互換；第二趟從第二個(gè)數(shù)據(jù)開始向后掃描，選擇最小的與第二個(gè)數(shù)據(jù)互換；依次進(jìn)行下去，進(jìn)行了(n-1)趟掃描以后就完成了整個(gè)排序過程。它比起冒泡排序有一個(gè)優(yōu)點(diǎn)就是不用不斷的交換。
程序1：直接插入法實(shí)現(xiàn)對(duì)數(shù)組的排序！
#include<stdio.h>
#include<conio.h>
int main()
{
void InsertSort(int [],int);
int a[7]={8,10,2,3,1,7,13};
int i;
InsertSort(a,7);
for(i=0;i<7;i++)
printf("%4d",a[i]);
getch();
}
void InsertSort(int a[],int count)
{
int i,j,temp;
for(i=1;i<count;i++)
{
temp=a[i];
j=i-1;
while(a[j]>temp && j>=0)
{
a[j+1]=a[j];
j--;
}
if(j!=(i-1))
a[j+1]=temp;
}
}
程序2：冒泡法實(shí)現(xiàn)對(duì)數(shù)組的排序！
#include<stdio.h>
#include<conio.h>
int main()
{
void BubbleSort(int []);
int a[10];
int i,j,temp;
printf("Input tem integer numbers for a[10]:");
for(i=0;i<10;i++)
scanf("%d,",&a[i]);
printf("\n");
BubbleSort(a);
printf("The sorted array is:\n");
for(j=0;j<10;j++)
printf("%d,",a[j]);
printf("\n\n");
getch();
}
void BubbleSort(int array[])
{
int i,j,temp;
for(j=0;j<9;j++)
for(i=0;i<9-j;i++)
if(array[i]>array[i+1])
{
temp=array[i];
array[i]=array[i+1];
array[i+1]=temp;
}
}
程序3：快速排序法實(shí)現(xiàn)對(duì)數(shù)組的排序！
#include<stdio.h>
#include<conio.h>
#define Max 8
int main()
{
void QuickSort(int a[],int p,int r);
int a[]={2,8,7,1,3,5,6,4};
QuickSort(a,1,Max);
printf(" The sorted array is :");
for(int i=0;i<Max;i++)
printf("%d,",a[i]);
printf("\n");
getch();
}
void QuickSort(int a[],int p,int r)
{
int Partition(int a[],int p,int r);
if(p<r)
{
int q=Partition(a,p,r);
QuickSort(a,p,q-1);
QuickSort(a,q+1,r);
}
}
int Partition(int a[],int p,int r)
{
int i=p-1;
int x=a[r-1];
for(int j=p;j<r;j++)
{
if(a[j-1]<=x)
{
i=i+1;
int temp;
temp=a[j-1];
a[j-1]=a[i-1];
a[i-1]=temp;
}
}
int temp;
temp=a[i];
a[i]=a[r-1];
a[r-1]=temp;
return i+1;
}
程序4：直接選擇法實(shí)現(xiàn)對(duì)數(shù)組的排序！
#include<stdio.h>
#include<conio.h>
int main()
{
void ChooseSort(int []);
int i,j,a[10];
printf("Input ten integer numbers for a[10]: ");
for(i=0;i<10;i++)
scanf("%d,",&a[i]);
printf("\n");
ChooseSort(a);
printf("The sorted array is:\n");
for(j=0;j<10;j++)
printf("%d,",a[j]);
printf("\n\n");
getch();
}
void ChooseSort(int array[])
{
int j,temp,*p1,*p2;
for(p1=array;p1<array+9;p1++)
{
j++;
for(p2=array+j;p2<=array+9;p2++)
if(*p2<*p1)
{
temp=*p2;
*p2=*p1;
*p1=temp;
}
}
}
各種排序方法的綜合比較：
一、時(shí)間性能
按平均的時(shí)間性能來分，四種類排序方法時(shí)間復(fù)雜度分別為：
直接插入排序法：O(n^2)，冒泡排序法：O(n^2)快速排序法：O(nlogn)，直接選擇排序法：O(n^2)
時(shí)間復(fù)雜度為O(n^2)的有：直接插入排序、起泡排序和簡單選擇排序，其中以直接插入為最好，特別是對(duì)那些對(duì)關(guān)鍵字近似有序的記錄序列尤為如此；當(dāng)待排記錄序列按關(guān)鍵字順序有序時(shí)，直接插入排序和起泡排序能達(dá)到O(n)的時(shí)間復(fù)雜度;而對(duì)于快速排序而言，這是最不好的情況，此時(shí)的時(shí)間性能蛻化為O(n2)，因此是應(yīng)該盡量避免的情況。
二、排序方法的穩(wěn)定性能
1. 穩(wěn)定的排序方法指的是，對(duì)于兩個(gè)關(guān)鍵字相等的記錄，它們?cè)谛蛄兄械南鄬?duì)位置，在排序之前和經(jīng)過排序之后，沒有改變。
2. 當(dāng)對(duì)多關(guān)鍵字的記錄序列進(jìn)行LSD方法排序時(shí)，必須采用穩(wěn)定的排序方法。
3. 對(duì)于不穩(wěn)定的排序方法，只要能舉出一個(gè)實(shí)例說明即可。
4. 快速排序是不穩(wěn)定的排序方法。