排序算法简记

//直接插入排序
void InsertSort(int data[], int n) {
    int i, j, temp;
    for (i = 1; i < n; i++) { //从第二个元素开始比较
        if (data[i] < data[i - 1]) { //后一个元素与前一个元素比较
            temp = data[i]; //临时保存较小的值
            for (j = i - 1; j >= 0 && data[j] > temp; j--) //往有序序列最后一个元素开始向前找位置
                data[j + 1] = data[j]; //元素后移
            data[j + 1] = temp; //插入位置
        }
    }
}

//折半插入排序
void BanInsertSort(int data[], int n) {
    int i, j, temp, low, mid, high;
    for (i = 1; i < n; i++) {
        if (data[i] < data[i - 1]) {
            temp = data[i];
            low = 0, high = i - 1;
            while (low <= high) { //与直接插入的区别是用折半查找的方式在有序序列中找到位置
                mid = (low + high) / 2;
                if (data[mid] > temp)
                    high = mid - 1;
                else
                    low = mid + 1;
            }
            for (j = i - 1; j >= high + 1; j--)  //high + 1 最后插入的位置
                data[j + 1] = data[j];
            data[high + 1] = temp;
        }
    }
}

//希尔排序
void ShellSort(int data[], int n) {
    int temp, j;
    for (int d = n / 2; d >= 1; d /= 2) { //确定步长
        for (int i = d ; i < n; i++) { //各个小子集内实际上是直接插入排序
            if (data[i] < data[i - d]) {
                temp = data[i];
                for (j = i - d; j >= 0 && data[j] > temp; j -= d)
                    data[j + d] = data[j];
                data[j + d] = temp;
            }
        }
    }
}
//冒泡排序
void swap(int *a, int *b) { //交换元素值
    int temp;
    temp = *a;
    *a = *b;
    *b = temp;
}

void BubbleSort(int data[], int n) {
    for (int i = 0; i < n - 1; i++) { //冒泡趟数，最多n-1趟
        for (int j = n-1; j > i; j--) { //从最后开始向前扫描
            if (data[j] < data[j - 1]) //交换
                swap(&data[j], &data[j - 1]);
        }
    }
}
//快速排序
int partition(int data[], int low, int high) {
    int pivot = data[low]; //将第一个值作为枢纽值，用pivot暂存
    while (low < high) {   //扫描
        while (low < high && data[high] >= pivot) //先从后扫描，只要扫到比枢纽值小的就交换
            high--;
        data[low] = data[high];
        while (low < high && data[low] <= pivot) //从前往后扫描，只要扫到比枢纽值大的就交换
            low++;
        data[high] = data[low];
    }
    data[low] = pivot; //枢纽值的最终位置
    return low;
}

void QuickSort(int data[],int low,int high){
    if(low<high){
        int mid = partition(data,low,high);
        QuickSort(data,low,mid-1);
        QuickSort(data,mid+1,high);
    }
}
//选择排序
void SelectSort(int data[], int n) {
    int i, j, min;
    for (i = 0; i < n - 1; i++) {
        min = i; //暂时将第一个记为最小值
        for (j = i + 1; j < n; j++) {
            if (data[j] < data[min])
                min = j; //更新最小值
        }
        if(min!=i)
            swap(&data[min],&data[i])
    }
}
//堆排序
void HeadAdjust(int data[], int i, int n) {
    int j;
    data[0] = data[i]; //保存根节点
    for (j = 2 * i; j <= n; j *= 2) { //从当前节点的左孩子开始比较并进一步向下比较
        if (j < n && data[j] < data[j + 1]) //如果左孩子小于右孩子，则右孩子最大
            j++;
        if (data[0] >= data[j]) //根已最大
            break;
        else {
            data[i] = data[j]; //将最大值上移
            i = j; //将此时的孩子看作根节点，便于继续向下调整，看向下调整的结点是否还要继续向下调整
        }
    }
    data[i] = data[0]; //最终位置
}

void BuildMaxHeap(int data[], int n) {
    int i;
    for (i = n / 2; i > 0; i--) {
        HeadAdjust(data, i, n); //反复调整堆
    }
}

void swap(int *a, int *b) { //交换元素值
    int temp;
    temp = *a;
    *a = *b;
    *b = temp;
}

void HeapSort(int data[], int n) {
    BuildMaxHeap(data, 8);
    for (int i = n; i > 1; i--) {
        swap(&data[i], &data[1]);
        HeadAdjust(data, 1, i - 1);
    }
}
//归并排序
int *copy = (int *) malloc(8 * sizeof(int));

void Merge(int data[], int low, int mid, int high) {
    int i, j, k;
    for (k = low; k <= high; k++)
        copy[k] = data[k];
    for (i = low, j = mid + 1, k = i; i <= mid && j <= high; k++) {
        if (copy[i] <= copy[j])
            data[k] = copy[i++];
        else
            data[k] = copy[j++];
    }
    while (i <= mid)
        data[k++] = copy[i++];
    while (j <= high)
        data[k++] = copy[j++];
}

void MergeSort(int data[], int low, int high) {
    if (low < high) {
        int mid = (low + high) / 2;
        MergeSort(data, low, mid);
        MergeSort(data, mid + 1, high);
        Merge(data, low, mid, high);
    }
}