1.插入排序

待排序數(shù)組從arr[1]向后遍歷，“插入”是指將待排序元素插在已排序元素中某個(gè)合適的位置，其中arr[0]視作已排序元素。插入排序與打撲克牌時(shí)的理牌比較相似，但不同的是，人能一眼看出待排序的那張牌需要插入的位置，而機(jī)器需要通過(guò)不斷比較大小和移動(dòng)元素來(lái)達(dá)到插入的目的。順序排序下，如果待排序元素小于前一個(gè)元素，則將前一個(gè)元素向后移動(dòng)一位，否則進(jìn)入到下一個(gè)待排序元素的操作中直至排序完成。

插入排序.gif

python實(shí)現(xiàn)：

def insert_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >=0 and key < arr[j] : 
            arr[j + 1] = arr[j]  # 等同于將arr[j]向后移一位
            j -= 1
        arr[j+1] = key

c++實(shí)現(xiàn)：

void insert_sort2(int arr[], int len){
    clock_t time_start=clock();
    for(int i=1;i<len;i++){
        int key = arr[i];
        int j = i-1;  
        while(j>=0 && (key < arr[j])){
            arr[j+1] = arr[j]; // 等同于將arr[j]向后移一位
            j--;
        }
        arr[j+1]=key; 
    }
}

2.希爾排序

希爾排序，也稱遞減增量排序算法，是插入排序的一種更高效的改進(jìn)版本。希爾排序的基本思想是：先將整個(gè)數(shù)組按照間隔 gap 分成若干子序列分別進(jìn)行插入排序，待整個(gè)數(shù)組"基本有序"時(shí)，再對(duì)該數(shù)組進(jìn)行插入排序。

希爾排序.png

python實(shí)現(xiàn)：

def shell_sort(arr): 
    n = len(arr)
    gap = int(n/2) # 先將間隔gap定位數(shù)組長(zhǎng)度的一半
    while gap > 0: 
        for i in range(gap, n): 
            key = arr[i]
            j = i - gap
            while  j >= 0 and key < arr[j]: 
                arr[j+gap] = arr[j]
                j -= gap
            arr[j+gap] = key
        gap = int(gap/2)

c++實(shí)現(xiàn)：

void shell_sort(int arr[], int len){
    int gap = int(len/2); // 先將間隔gap定位數(shù)組長(zhǎng)度的一半
    while(gap > 0){
        for(int i=gap;i<len;i++){
            int key = arr[i];
            int j = i - gap;
            while(j>=0 && key<arr[j]){
                arr[j+gap] = arr[j];
                j -= gap;
            }
            arr[j+gap] = key;
        }
        gap = int(gap/2);
    }
}