排序分為內部排序和外部排序，內部排序指待排序的記錄在內存中，外部排序的記錄數量很大，以至于內存放不下而放在外存中，排序過程需要訪問外存。這里僅介紹內部排序，包括插入排序、交換排序、選擇排序、歸并排序、基數排序。

1 插入排序

1.1直接插入（straight insertion sort）

算法思路：數組｛k1,k2,……，kn｝，排序一開始k1是一個有序序列，讓k2插入得到一個表長為2的有序序列，依此類推，最后讓kn插入上述表長為n－1的有序序列，得到表長為n的有序序列。

c實現的代碼：

//    從小到大排序

    int a[]={98,97,34,345,33};

    int k=sizeof(a)/sizeof(a[0]);

    int j;

    for (int i=1; i<k; i++) {

        int temp=a[i];

        for (j=i-1; j>=0&&a[j]>temp; j--) {

            a[j+1]=a[j];

        }

        a[j+1]=temp;

    }

1.2折半插入（binary insertion sort）

算法思路：當直接插入進行到某一趟時，對于r［i］來講，前面i－1個記錄已經按關鍵字有序。此時不用直接插入排序的方法，而改為折半查找，找出r［i］應插入的位置。

c實現的代碼：

//    從小到大排序

void binasort(int r[100],int n){

    for (int i=1; i<n; i++) {

        int temp =r[i];

        int low=0;

        int high=i-1;

        while (low<=high) {

            int middle=(low+high)/2;

            if (temp<r[middle]) {

                high=middle-1;

            }else{

                low=middle+1;

            }

        }

        for (int j=i-1; j>=low; j--) {

            r[j+1]=r[j];

        }

        r[low]=temp;

    }

}

1.3希爾排序（shell sort）

算法思路：“縮小增量”的排序方法，初期選用增量較大間隔比較，然后增量縮小，最后為1，希爾排序對增量序列沒有嚴格規定。設有組關鍵字｛99，22，33，333，2，3，23，44｝，由小到大排序，這里n＝8，先第一個個增量取d1=4，那么記錄分為4組，第一組 r［0］，r［4］，第二組r［1］，r［5］，……在各組內部使用插入排序，使得每組內是有序的，接著取d2=2，分為兩組，d3=1,最后就編程有序序列。

c語言實現的代碼：

//    從小到大排序

void shellsort(int r[100],int n){

    int k=n/2;

    while (k>0) {

        for (int i=k; i<n; i++) {

            int temp=r[i];

            int j=i-k;

            while ((r[j]>temp)&&(j>=0)) {

                r[j+k]=r[j];

                j=j-k;

            }

            r[j+k]=temp;

            

        }

        k/=2;

        

    }

}

2 交換排序

2.1冒泡排序（bubble sort）

算法思路：在排序過程，關鍵字較小的記錄經過與其他記錄的對比交換，好像水中的氣泡一樣，移到數據序列的最前面。

c語言實現的代碼：

//    從小到大排序

void bubblesort(int r[100],int n){

    for (int i=0; i<n-1; i++) {

        for (int j=0; j<n-1-i; j++) {

            if (r[j]>r[j+1]) {

                int temp=r[j];

                r[j]=r[j+1];

                r[j+1]=temp;

            }

        }

    }

}

2.2快速排序(quick sort)

算法思路：通過一趟排序將要排序的數據分割成獨立的兩部分，其中一部分的所有數據比另外一部分的所有數據都要小，然后再按此方法對這兩部分數據分別進行快速排序。整個排序過程可以遞歸實現，也可以非遞歸實現。

c語言實現遞歸的快速排序的代碼：

//    從小到大排序

void quickSort(int a[],int numsize){

    int i=0,j=numsize-1;

    int val=a[0];//指定參考值val大小

    if (numsize>1) { //確保數組長度至少為2，否則無需排序

        while (i<j) {//循環結束條件

//            從后向前搜索比val小的元素，找到后填到a［i］中并跳出循環

            for (; j>i; j--) {

                if (a[j]<val) {

                    a[i]=a[j];

                    break;

                }

            }

//            從前向后搜索比val大的元素，找到后填到a［j］中并跳出循環

            for (; i<j; i++) {

                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－1-i個數排序

    }

    

}

3 選擇排序

3.1 簡單選擇排序（simple selection sort）

算法思路：對于一組關鍵字｛k1，k2，……kn｝，將其從小到大排序，首先從k1，k2，……k3中選擇最小值Kz，在將Kz與k1對換；然后從k2……Kn中選最小值Kz，與k2交換。如此選擇和調換n－2趟，第n－1趟只要調換Kn-1 和Kn比較就好了。

c語言實現的代碼：

//從小到大排序

void sisort(int r[100],int n){

    for (int i=0; i<n-1; i++) {

        int z=i;

        for (int j=i+1; j<n; j++) {

            if (r[z]>r[j]) {

                z=j;

            }

        }

        if (z!=i) {

            int temp=r[i];

            r[i]=r[z];

            r[z]=temp;

        }

    }

}

3.2堆排序（heap sort）

算法思路：堆有兩個性質，一是堆中某個節點的值總是不大于或不小于其父節點的值，二是堆是一棵完全樹。以從大到小排序為例，首先要把得到的數組構建為一個最小堆，這樣父節點均是大于或者等于子結點，根節點就是最小值，然后讓根節點與尾節點交換，這樣一次之后，再把前n－1個元素構建出最小根堆，讓根結點與第n－2個元素交換，依此類推，得到降序序列。

c語言實現代碼：

//從大到小排序

//以i節點為根，調整為堆的算法，m是節點總數，i節點的子結點為i*2+1,i*2+2

void heapMin(int r[100],int i,int m){

//    temp保存根節點，j為左孩子編號

    int j,temp;

    temp=r[i];

    j=2*i+1;

    

    while (j<m) {

        if (j+1<m && r[j+1]<r[j]) {//在左右孩子中找最小的

            j++;

        }

        if (r[j]>=temp) {

            break;

        }

        

        r[i]=r[j];

        i=j;

        j=2*i+1;

        

    }

    r[i]=temp;

    

}

 

void heapSort(int r[100],int n){

//   n/2-1最后一個非葉子節點

//   下面這個操作是建立最小堆

    for (int i=n/2-1; i>=0; i--) {

        heapMin(r, i, n);

    }

//   一下for語句為輸出堆頂元素，調整堆操作

    for (int j=n-1; j>=1; j--) {

 

        

//   堆頂與堆尾交換

        int temp=r[0];

        r[0]=r[j];

        r[j]=temp;

        

        heapMin(r, 0, j);

    }

    

//得到的就是降序序列

    for (int i=0; i<n; i++) {

        printf(" %d",r[i]);

    }

}

參考網址：http://blog.csdn.net/morewindows/article/details/6709644

4 歸并排序（merge sort）

4.1兩路歸并排序

算法思路：它指的是將兩個順序序列合并成一個順序序列的方法。如有數列｛6，202，100，301，38，8，1｝，第一次歸并后變成了｛6，202｝，｛100，301｝，｛8，38｝，｛1｝；第二次歸并后，｛6，100，202，301｝，｛1，8，38｝；第三次歸并后｛1，6，8，38，100，202，301｝。

5 基數排序（radix sort）

算法思路：

    基數排序可以采用LSD（Least significant digital）或者MSD（Most significant digital），LSD的排序由鍵值的最右邊開始，MSD從最左邊開始。

    以LSD為例，假設原來有一串數值如下所示：

    73, 22, 93, 43, 55, 14, 28, 65, 39, 81

    第一步

    首先根據個位數的數值，在走訪數值時將它們分配至編號0到9的桶子中：

    0

    1 81

    2 22

    3 73 93 43

    4 14

    5 55 65

    6

    7

    8 28

    9 39

    第二步

    接下來將這些桶子中的數值重新串接起來，成為以下的數列：

    81, 22, 73, 93, 43, 14, 55, 65, 28, 39

    接著再進行一次分配，這次是根據十位數來分配：

    0

    1 14

    2 22 28

    3 39

    4 43

    5 55

    6 65

    7 73

    8 81

    9 93

    第三步

    接下來將這些桶子中的數值重新串接起來，成為以下的數列：

    14, 22, 28, 39, 43, 55, 65, 73, 81, 93

    這時候整個數列已經排序完畢；如果排序的對象有三位數以上，則持續進行以上的動作直至最高位數為止。

    LSD的基數排序適用于位數小的數列，如果位數多的話，使用MSD的效率會比較好。