插入排序

直接插入排序

把$n$个待排序的元素假设为一个有序表和一个无序表，开始时有序表中只包含1个元素，无序表中包含有n-1个元素，排序过程中每次从无序表中取出第一个元素，将它插入到有序表中的适当位置，使之成为新的有序表，重复n-1次即可完成排序过程

void insertSort(int array[],int n) {
    int i, j, key;
    for (i = 1; i < n; i++) {
        if (array[i] < array[i - 1]) {
            key = array[i];//设置为哨兵
            //找到合适的插入位置并将比key大的元素后移
            for (j = i - 1; key < array[j] && j >= 0; --j)
                array[j + 1] = array[j];
            array[j + 1] = key;//插入
        }
    }
}

折半插入排序

void insertSortbyHalf(int array[],int n){
    int i,j,key,mid,low,high;
    for (i = 1; i < n; i++) {
        if(array[i] < array[i-1]){
            key = array[i];
            low = 0,high = i-1;
              //找到插入的位置
            while(low <= high){
                mid = (low + high) / 2;
                if(key < array[mid])
                    high = mid - 1;
                else
                    low = mid + 1;
            }
              //统一移动元素
            for(j = i-1;j >= high+1;j--){
                array[j+1] = array[j];
            }
            array[j+1] = key;//插入
        }
    }
}

希尔排序

增量序列 $d1，d_2，\cdots，d_k$，其中 $d_1=n/2,d{i+1}=[d_i/2],d_k = 1$；

按增量序列个数 $k$，对序列进行 $k$ 趟排序；

每趟排序，先根据对应的增量 $d_i$，将待排序序列分割为$d_i$个组，距离为$d_i$的元素为同一组，再对每个组进行直接插入排序，直到$d_i =1$,即所有元素已在同一组中，再进行一次直接插入排序

void shellSort(int array[],int n) {
    int di, i,j, key;
    for (di = n/2; di >= 1; di = di/2) {//设置增量
        //分组并进行插入排序
        for (i = di; i < n; i++) {
            if (array[i] < array[i - di]) {
                key = array[i];
                for (j = i - di; j >= 0 && key < array[j]; j = j - di) {
                    array[j + di] = array[j];
                }
                array[j + di] = key;
            }
        }
    }
}

交换排序

冒泡排序

每次比较两个相邻的元素，如果其顺序错误就交换

void bubbleSort(int array[],int n) {
    int key;
    for (int i = 0; i < n-1;i++) {
        //LEN-i:每一次都已归位一个数,不再需要与已归位的数比较
        for (int j = 0; j < n - i - 1; j++) {
            if (array[j] > array[j + 1]) {
                key = array[j];
                array[j] = array[j + 1];
                array[j + 1] = key;
            }
        }
    }
}

快速排序

1.设置两个变量$i,j$，初始化：$i=0，j=n-1$；
2.基准数 $key=array[0]$ ；
3.从 $j$ 开始向前搜索，即由后开始向前搜索 $(j—)$ ，找到第一个小于 $key$ 的值 $array[j]$ ，将 $array[j]$ 和 $array[i]$ 的值交换；
4.从 $i$ 开始向后搜索，即由前开始向后搜索 $(i++)$ ，找到第一个大于key的 $array[i]$ ，将 $array[i]$ 和 $array[j]$ 的值交换；
5.重复第3、4步，直到 $i=j$ ；

经过一趟上述步骤后，基准数左边全小于基准数，基准数右边全大于基准数，通过分治法继续处理左、右

void quickSort(int array[], int left, int right){
    if (left >= right){
        return;
    }
    int i = left;
    int j = right;
    int key = array[left];//基准数

    while (i < j){
        //向前寻找小于key的数
        while (i < j && key <= array[j]){
            j--;
        }
        array[i] = array[j];
        //向后寻找大于key的数
        while (i < j && key >= array[i]){
            i++;
        }
        array[j] = array[i];
    }
    array[i] = key;//基准数归位
    quickSort(array, left, i - 1);//分治处理左边
    quickSort(array, i + 1, right);//分治处理右边
}

选择排序

简单选择排序

(1)在未排序序列中找到最小/大元素，存放到排序序列的起始位置;(2)再从剩余未排序元素中继续寻找最小/大元素，放到已排序序列的末尾;重复第二步，直到所有元素均排序完毕

void selectSort(int array[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int min = i;
        for (int j = i + 1; j < n; j++) {
            if (array[j] < array[min])
                min = j;
        }
        if (i != min) {
            int temp = array[i];
            array[i] = array[min];
            array[min] = temp;
        }
    }
}

堆排序

堆是具有以下性质的完全二叉树：

1.每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；

2.每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆；

堆排序算法步骤：

1.构造初始堆，将无序序列构造为大顶堆，从倒数第一个非叶子结点开始调整,从左至右，从下至上进行调整；

倒数第$i$个非叶子结点索引$index=array.length/2^i-1(i=1,2,3\dots|2^i\leqslant array.length)$

2.将堆顶元素与末尾元素进行交换，使末尾元素最大，然后继续调整堆，再将堆顶元素与末尾元素交换，得到第二大元素，如此反复进行交换、重建、交换…

void swap(int* a, int* b){
    int temp = *b;
    *b = *a;
    *a = temp;
}

void max_heapify(int array[], int start, int end){
    //建立父节点指标和子结点指标
    int dad = start;
    int son = dad * 2 + 1;
    while (son <= end){//若子结点索引在范围内才做比较
        //先比较两个子结点大小，选择最大的
        if (son + 1 <= end && array[son] < array[son + 1])
            son++;
        if (array[dad] > array[son]) //如果父节点大於子结点代表调整完毕，直接跳出函数
            return;
        else{
            swap(&array[dad], &array[son]);
            dad = son;
            son = dad * 2 + 1;
        }
    }
}

void heap_sort(int array[], int len){
    int i;
    //初始化，生成最大堆
    for (i = len / 2 - 1; i >= 0; i--)
        max_heapify(array, i, len - 1);

    //堆顶元素与末尾元素进行交换，再重新调整，直到排序完毕
    for (i = len - 1; i > 0; i--){
        swap(&array[0], &array[i]);
        max_heapify(array, 0, i - 1);
    }
}

归并排序

假定含有$n$个元素的待排序表，则可视为$n$个有序的子表，每个子表长度为1，然后两两归并，得到[$n/2$]个长度为2或1的有序表；再两两归并$\cdots$,直到合并长度为$n$的有序表为止

void merge(int array[], int low, int mid, int high, int temp[]){
    int i = low, j = mid + 1;
    int m = mid, n = high;
    int k = 0;
    while (i <= m && j <= n){
        if (array[i] <= array[j])
            temp[k++] = array[i++];
        else
            temp[k++] = array[j++];
    }
    while (i <= m)
        temp[k++] = array[i++];

    while (j <= n)
        temp[k++] = array[j++];

    for (i = 0; i < k; i++)
        array[low + i] = temp[i];
}
void mergesort(int array[], int low, int high, int temp[]){
    if (low < high){
        int mid = (low + high) / 2;
        mergesort(array, low, mid, temp);    
        mergesort(array, mid + 1, high, temp); 
        merge(array, low, mid, high, temp);
    }
}

---

---