JZTXT

排序算法

发布时间 2023-08-26 16:33:55作者: Zh'Blog

排序

插入排序

直接插入排序

//直接插入排序
void InsertSort(int A[], int n) {
   int i, j, temp;
   for (i = 1; i < n; i++) {  //将各元素插入已经排好序的序列中
       if (A[i] < A[i - 1]) { //若A[i]关键字小于前驱
           temp = A[i];       //用temp暂存A[i]
           for (j = i - 1; j >= 0 && A[j] > temp;
                j--) {          //检查所有前面已拍好序的元素
               A[j + 1] = A[j]; //所有大于temp的元素都向后移动
           }
           A[j + 1] = temp; //复制到插入位置
       }
   }
}
//直接插入排序(带哨兵)
void InsertSort2(int A[], int n) {
   int i, j;
   for (i = 2; i <= n; i++) { //元素下标为1-n,n个元素长度为n+1，所有此处i<=n
       if (A[i] < A[i - 1]) {
           A[0] = A[i];
           for (j = i - 1; A[j] > A[0]; j--) {
               A[j + 1] = A[j];
           }
           A[j + 1] = A[0];
       }
   }
}

折半插入排序

//折半插入排序(带哨兵)
void InsertSort3(int A[], int n) {
    int i, j, low, high, mid;
    for (i = 2; i <= n; i++) {
        A[0] = A[i];
        low = 1, high = i - 1; //设置折半查找范围
        //查找要插入的位置
        while (low <= high) {
            mid = (low + high) / 2;
            if (A[mid] > A[0])
                high = mid - 1;
            else
                low = mid + 1;
        }
        //将low到i-1位置的元素依次往后移
        for (j = i - 1; j >= low; j--) {
            A[j + 1] = A[j];
        }
        A[low] = A[0];
    }
}

希尔排序

//希尔排序
void ShellSort(int A[], int n) {
    int i, j, d;
    //A[0]只是暂存单元，不是哨兵
    for (d = n / 2; d >= 1; d /= 2) { //增量变化
        for (i = d + 1; i <= n; i++) {
            if (A[i] < A[i - d]) {
                A[0] = A[i];
                for (j = i - d; j > 0 && A[0] < A[j]; j -= d) {
                    A[j + d] = A[j];
                }
                A[j + d] = A[0];
            }
        }
    }
}

交换排序

冒泡排序

void swap(int& a, int& b) {
    int temp = a;
    a = b;
    b = temp;
}
//从后往前:每趟处理都会将最小元素放在最终位置
void BubbleSort(int A[], int n) {
    for (int i = 0; i < n - 1; i++) {
        bool flag = false;
        for (int j = n - 1; j > i; j--) { //一趟冒泡过程
            if (A[j - 1] > A[j]) {        //若为逆序
                swap(A[j - 1], A[j]);     //交换
                flag = true;
            }
        }
        if (flag == true) { //本趟遍历后没有发生变化，说明表已经有序
            return;
        }
    }
}
//从前往后:每趟处理都会将最大元素放在最终位置
void BubbleSort2(int A[], int n) {
    for (int i = 0; i < n - 1; i++) {
        bool flag = false;
        for (int j = i; j < n - 1; j++) {
            if (A[j] > A[j + 1]) {
                swap(A[j], A[j + 1]);
                flag = true;
            }
        }
        if (flag == false) { //本趟遍历后没有发生变化，说明表已经有序
            return;
        }
    }
}

快速排序

//使用第一个元素将排序序列划分成左右两个部分
int Partition(int A[], int low, int high) {
    int pivot = A[low]; //用第一个元素作为枢纽
    /*
     *确定枢纽元素位置的思路:
     *移动high指针，直到找到比枢纽元素小的元素,执行A[low] = A[high]
     *然后移动low指针，直到找到比枢纽元素大的元素,执行A[high] = A[low]
     *然后再移动high指针.......，循环以上操作，直到low=high为止，
     *low或high即为枢纽元素位置
     */
    while (low < high) { //找出枢纽元素的位置
        while (low < high &&
               A[high] >= pivot) //移动high指针，直到找到比枢纽元素小的元素
            --high;
        A[low] = A[high];
        while (low < high &&
               A[low] <= pivot) //移动low指针，直到找到比枢纽元素大的元素
            ++low;
        A[high] = A[low];
    }
    A[low] = pivot; //枢纽元素存放到最终位置
    return low;
}
void QuickSort(int A[], int low, int high) {
    if (low < high) {//递归跳出的条件
        int pivotpos =Partition(A, low, high); //划分，获取枢纽元素的位置
        QuickSort(A, low, pivotpos-1);//划分左子表
        QuickSort(A, pivotpos+1, high);//划分右子表
    }
}