問題：數組排序（即按某種特定的順序排列數據，如升序或降序）是最重要的計算應用之一，銀行用帳號對所有的支票進行能夠排序，并根據排序結果準備月底的財務報告，學校學生成績管理系統用數組排序的方法將考試成績從高到低進行排名，數組排序方法很多，有直接插入排序、冒泡排序、快速排序、直接選擇排序，下面來詳細介紹這四種基本的排序方法及其實現。
1，直接插入排序：當數據表A中每個元素距其最終位置不遠，數據表A按關鍵字值基本有序，可用此方法排序較快。
2，冒泡排序法：將較小的值“上浮”到數組頂部，而較大值“下沉”到數組底部，這種排序技術要比較好幾趟，每一趟要比較連續的數組元素對，如果某對數值是按升序排序的（或者這兩個值相等），那就保持原樣，如果某對數組是按降序排列的，就要交換它們的值。
3，快速排序法：快速排序是對冒泡排序的一種改進。它的基本思想是：通過一躺排序將要排序的數據分割成獨立的兩部分，其中一部分的所有數據都比另外一部分的所有數據都要小，然后再按次方法對這兩部分數據分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數據變成有序序列。
4，直接選擇排序法：直接選擇排序的作法是：第一趟掃描所有數據，選擇其中最小的一個與第一個數據互換；第二趟從第二個數據開始向后掃描，選擇最小的與第二個數據互換；依次進行下去，進行了(n-1)趟掃描以后就完成了整個排序過程。它比起冒泡排序有一個優點就是不用不斷的交換。
程序1：直接插入法實現對數組的排序！
#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：冒泡法實現對數組的排序！
#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：快速排序法實現對數組的排序！
#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：直接選擇法實現對數組的排序！
#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;
}
}
}
各種排序方法的綜合比較：
一、時間性能
按平均的時間性能來分，四種類排序方法時間復雜度分別為：
直接插入排序法：O(n^2)，冒泡排序法：O(n^2)快速排序法：O(nlogn)，直接選擇排序法：O(n^2)
時間復雜度為O(n^2)的有：直接插入排序、起泡排序和簡單選擇排序，其中以直接插入為最好，特別是對那些對關鍵字近似有序的記錄序列尤為如此；當待排記錄序列按關鍵字順序有序時，直接插入排序和起泡排序能達到O(n)的時間復雜度;而對于快速排序而言，這是最不好的情況，此時的時間性能蛻化為O(n2)，因此是應該盡量避免的情況。
二、排序方法的穩定性能
1. 穩定的排序方法指的是，對于兩個關鍵字相等的記錄，它們在序列中的相對位置，在排序之前和經過排序之后，沒有改變。
2. 當對多關鍵字的記錄序列進行LSD方法排序時，必須采用穩定的排序方法。
3. 對于不穩定的排序方法，只要能舉出一個實例說明即可。
4. 快速排序是不穩定的排序方法。