1 插入排序

1.1 直接插入排序

直接插入排序的基本思想是：把数组a[n]中待排序的n个元素看成一个有序表和一个无序表，排序过程中每次从无序表中取出第一个元素插入到有序表的适当位置，直至无序表变为空表。
直接插入排序，时间复杂度为O(n^2)。
具体代码如下：

void straight_insertion_sort(int a[], const int start, const int end) {
    int tmp;
    int i, j;
    for (i = start + 1; i < end; i++) {
        tmp = a[i];
        for (j = i - 1; tmp < a[j] && j >= start; j--) {
            a[j + 1] = a[j];
        }
        a[j + 1] = tmp;
    }
} 

1.2 折半插入排序

在查找插入位置的时候，如果运用折半查找，则为折半插入排序。其时间复杂度为O(nlog2n)。
具体的代码如下：

void binary_insertion_sort(int a[], const int start, const int end{
    int tmp;
    int i, j, left, right, mid;
    for(i=start+1; i<end;i++){
        tmp=a[i];
        left=start;
        right=i-1;
        while(left<=right){
            mid=(left+right)/2;
            if(tmp<a[mid])
                right=mid-1;
            else
                left=mid+1;
        }
        for(j=i-1;j>=left;j--)
            a[j+1]=a[j];
        a[left]=tmp;
    }
}

1.3 希尔插入排序

希尔排序的基本思想是：将n个元素的序列，按gap=[n/3]+1作为间隔，所有距离为gap的元素放在一个子序列中进行直接插入排序，然后gap=[gap/3]+1缩小，直到gap=1为止。
排序过程如下：

image.png
具体代码如下：

static void shell_insert(int a[], const int start, const int end, const int gap){
    int tmp;
    int i, j;
    for(i=start+gap;i<end;i+=gap){
        tmp=a[i];
        for(j=a-gap;j>=start&&tmp<a[j];j-=gap){
            a[j+gap]=a[j];
        }
        a[j+gap]=tmp;
    }
}

void shell_sort(int a[], const int start, const int end){
    int gap=end-start;
    while(gap>1){
        gap=gap/3+1;
        shell_insert(a, start, end, gap);
    }
}

2 交换排序

2.1 冒泡排序

冒泡排序的基本方法是：设待排序元素序列的元素个数为n，从后向前两两比较相邻元素的值，如果发生逆序（即前一个比后一个大），则交换它们，直到序列比较完。我们称它为一趟冒泡，结果是最小的元素交换到待排序序列的第一个位置，其他元素也都向排序的最终位置移动。下一趟冒泡时前一趟确定的最小元素不参加比较，待排序序列减少一个元素，一趟冒泡的结果又把序列中最小的元素交换到待排序序列的第一个位置。这样最多做n-1 趟冒泡就能把所有元素排好序。

void bubble_sort(int a[], const int start, const int end){
    int tmp;
    int i, j;
    
    for(i=0;i<end;i++){
        for(int j=end-1;j>i;j--){
            if(a[j-1]>a[j]){
                tmp=a[j-1];
                a[j-1]=a[j];
                a[j]=tmp;
            }
        }
    }
}

2.2 快速排序

快速排序的基本思想是任取待排序元素序列中的某个元素（例如取第一个元素）作为基准，按照该元素的关键字大小，将整个元素序列划分为左右两个子序列：左侧子序列中所有元素的关键字都小于基准元素的关键字，右侧子序列中所有元素的关键字都大于或等于基准元素的关键字，基准元素则排在这两个子序列中间（这也是该元素最终应该安放的位置）。然后分别对这两个子序列重复施行上述算法，直到所有的元素都排在相应位置为止。
排序过程如下：

image.png
具体的代码实现如下：

int partition(int a[], const int start, const int end){
    int i=start;
    int j=end-1;
    const int pivot=a[i];

    while(i<j){
        while(i<j&&a[j]>=pivot)
            j--;
        a[i]=a[j];
        while(i<j&&a[i]<=pivot)
            i++;
        a[j]=a[i];
    }
    a[i]=pivot;
    return i;
}
void quick_sort(int a[], const int start, const int end){
    if(start<end-1){
        const int pivot_pos=partition(a, start, end);
        quick_sort(a, start, pivot_pos);
        quick_sort(a, pivot+1, end); 
    }
}

3 选择排序

选择排序的基本思想是：每一趟在后面n-i(i=1, 2, …, n-2) 个元素中选取最小的元素作为有序序列的第i 个元素。

3.1 简单选择排序

简单选择排序也叫直接选择排序，其基本步骤是：

• 在一组元素a[i] a[n-1] 中选择最小的元素；
• 若它不是这组元素中的第一个元素，则将它与这组元素的第一个元素对调；
• 在剩下的a[i+1] a[n-1] 中重复执行以上两步，直到剩余元素只有一个为止。
  具体实现代码如下：

void simple_selection_sort(int a[], const int start, const int end){
    int tmp;
    int i, j, k;
    for(i=start;i<end;i++){
        k=i;
        for(j=i+1;j<end;j++){
            if(a[j]<a[k])
                k=j;
        }
        if(k!=i){
            tmp=a[i];
            a[i]=a[k];
            a[k]=tmp;
        }
    }
}