排序算法总结

1. 插入排序

直接插入排序

在要排序的一组数中，假设前n-1个数已经拍好顺序，现将第n个数插到有序数列中，使这n个数也是排序好的，如此循环，直到全部排好顺序。O(n^2)
代码实现:

void InsertSort(int array[],int length){
    int temp;
    for(int i = 0;i < length - 1;i++){
        for(int j = i+1;j > 0;j++){
            if(array[j] < array[j-1]){
                temp = array[j-1];
                array[j-1] = array[j];
                array[j] = temp;
            }else{
                `break;
            }
        }
    }
}

希尔排序

2. 选择排序

简单排序

堆排序

3. 交换排序

冒泡

两个数比较大小，较大的书下沉，较小的数冒出。
过程：比较相邻数据，若第二个数小，就交换位置：从后向前两两比较，一直到比较最前两个数据最终最小数据被交换到起始位置，则第一个最小数位置排好：重复上述过程，将剩余数排好。
代码实现：

void BubbleSort(int arr[]){
    int temp;
    for(int i = 0;i < arr.length-1;i++){
        for(int j=arr.length-1;j>i;j--){
            if(arr[j]<arr[j-1]){
                temp = arr[j];
                arr[j] = arr[j-1];
                arr[j-1] = temp;
            }
        }
    }
}

优化：多数时候，数据排好顺序后，算法仍会进行下一轮比较，知道arr.length-1次，后面的比较无意义。此时可设置标志位flag，用于标志某一趟排序过程是否有数据交换，若未发生交换，则可立即结束排序。

void BubbleSort(int arr[]){
    int temp;
    for(int i = 0;i < arr.length-1;i++){
        bool flag = false;
        for(int j=arr.length-1;j>i;j--){
            if(arr[j]<arr[j-1]){
                temp = arr[j];
                arr[j] = arr[j-1];
                arr[j-1] = temp;
                flag = true;
            }
        }
        if(!flag)
            break;
    }
}

快速

4. 归并排序

5. 基数排序