经典排序算法（上）（冒泡排序、选择排序、插入排序）

1.冒泡排序

冒泡排序每趟排序让相邻元素两两比较选出一个最大（小）的值放到待排序的序列最后位置。

冒泡排序－图片来自维基百科

参考代码如下：

void bubbleSort(int a[],int length){
        for(int i = 0;i<length;i++){
            for(int j =0;j<length-i-1;j++){
                if(a[j]>a[j+1]){//相邻两个数比较
                    int temp = a[j];
                    a[j] = a[j+1];
                    a[j+1] = temp;      
                }
            }
        }
    }

排序过程如下所示：
初始状态：a[0]　　a[1]　　a[2]　　a[3]　　a[4]　　a[5]
初始值：　５　　　２　　　３　　　６　　　１　　　４
第一趟排序过程：
　　　　　５　　　２　　　３　　　６　　　１　　　４ (a[0]＞a[1]--交换)
　　　　　２　　　５　　　３　　　６　　　１　　　４ (a[1]＞a[2]--交换)
　　　　　２　　　３　　　５　　　６　　　１　　　４ (a[2]＜a[3]不交换)
　　　　　２　　　３　　　５　　　６　　　１　　　４ (a[3]＞a[4]--交换)
　　　　　２　　　３　　　５　　　１　　　６　　　４ (a[4]＞a[5]--交换)
　　　　　２　　　３　　　５　　　１　　　４　　　6 　(第一趟排序结果)
第二趟：　２　　　３　　　１　　　４　　　 5　　　6　
第三趟：　２　　　１　　　３　　　４　　　 5　　　6　
第四趟：　１　　　２　　　３　　　４　　　 5　　　6　
第五趟：　１　　　２　　　３　　　４　　　 5　　　6
第六趟：　１　　　２　　　３　　　４　　　 5　　　6

2.选择排序

（快速）选择排序每趟排序在待排序序列里选择一个最小的拿出来放到已排序序列的后面。

选择排序－图片来自维基百科

参考代码如下：

void selectionSort(int a[],int length){
        for(int i  = 0;i<length;i++){//第i趟--a[i]后所有数跟a[i]比较         
            for(int j = i+1;j<length;j++){//找到a[i]~a[length-1]中最小的数与a[i]交换
                if(a[i]>a[j]){
                    int temp = a[j];
                    a[j] = a[i];
                    a[i] = temp;
                }
            }
         }
    }

初始状态：a[0]　　a[1]　　a[2]　　a[3]　　a[4]　　a[5]
初始值：　５　　　２　　　３　　　６　　　１　　　４
第一趟排序过程：　
　　　　　５　　　２　　　３　　　６　　　１　　　４ (a[0]＞a[1]--交换)
　　　　　２　　　５　　　３　　　６　　　１　　　４ (a[0]＜a[2]不交换)
　　　　　２　　　５　　　３　　　６　　　１　　　４ (a[0]＜a[3]不交换)
　　　　　２　　　５　　　３　　　６　　　１　　　４ (a[0]＞a[3]--交换)
　　　　　１　　　５　　　３　　　６　　　２　　　４ (a[0]＜a[4]不交换)
　　　　　１　　　５　　　３　　　６　　　２　　　４ (第一趟排序结果)
第二趟：　１　　　２　　　５　　　６　　　３　　　４　
第三趟：　１　　　２　　　３　　　６　　　 5　　　４　
第四趟：　１　　　２　　　３　　　４　　　６　　　５　
第五趟：　１　　　２　　　３　　　４　　　 5　　　6
第六趟：　１　　　２　　　３　　　４　　　 5　　　6

3.插入排序

插入排序每趟排序取出待排序序列中的数，在已排序序列中从后向前扫描，找到相应位置并插入。

插入排序－图片来自维基百科

参考代码如下：

void insertSort(int a[],int length){
        for(int i = 1;i<length;i++){
            int temp  = a[i];//当j = i+1时往后放置一位可能将a[i]值覆盖，所以需要中间变量temp来暂存a[i]的值
            int j;
            for(j = i-1;j>=0&&a[j]>temp;j--){
                a[j+1] = a[j];//整体后移一位
                }
             a[j+1] = temp;//选中合适位置放置
            }
    }

初始状态：a[0]　　a[1]　　a[2]　　a[3]　　a[4]　　a[5]
初始值：　５　　　２　　　３　　　６　　　１　　　４
第一趟：　５　　　２　　　３　　　６　　　１　　　４
第二趟：　２　　　５　　　３　　　６　　　１　　　４ 　
第三趟：　２　　　３　　　５　　　６　　　１　　　４　
第四趟：　２　　　３　　　５　　　６　　　１　　　４　　
第五趟：　１　　　２　　　３　　　５　　　６　　　４
第六趟：　１　　　２　　　３　　　４　　　 5　　　6