排序技术

排序算法	平均时间复杂度	最好	最差	空间复杂度	稳定性
直接插入排序	O(n2)	O(n)	O(n2)	O(1)	稳定
冒泡排序	O(n2)	O(n)	O(n2)	O(1)	稳定
快速排序	O(n*log2n)	O(n*log2n)	O(n2)	O(log2n)	不稳定
简单选择排序	O(n2)	O(n2)	O(n2)	O(1)	不稳定
堆排序	O(n*log2n)	O(n*log2n)	O(n*log2n)	O(1)	不稳定
归并排序	O(n*log2n)	O(n*log2n)	O(n*log2n)	O(n)	稳定

插入排序

直接插入排序(straight insertion sert)

交换排序

冒泡排序(bubble sort)

void bubbleSort(vector<int> &a) {
    int exchange = a.size() - 1;// 第一趟冒泡排序的区间是[0,n-1]
    while (exchange > 0) {// 当上一趟排序有记录交换时
        int bound = exchange;
        exchange = 0;
        for (int i = 0; i < bound; i++) {// 一趟冒泡排序,排序区间是[0,bound-1]
            if (a[i] > a[i + 1]) {
                swap(a[i], a[i + 1]);
                exchange = i;// 记载每一次记录交换的位置
            }
        }
    }
}

快速排序(quick sort)

int partition(vector<int> &a, int front, int end) {
    while (front < end) {
        while (front < end && a[front] <= a[end]) {// 右侧扫描
            end--;
        }
        if (front < end) {
            swap(a[front], a[end]);// 将较小记录交换到前面
            front++;
        }
        while (front < end && a[front] <= a[end]) {// 左侧扫描
            front++;
        }
        if (front < end) {
            swap(a[front], a[end]);// 将较大记录交换到后面
            end--;
        }
    }
    return front;// 轴值记录的最终位置
}

void quickSort(vector<int> &a, int front, int end) {
    if (front < end) {// 区间长度大于1,执行一次划分,否则递归结束
        int pivot = partition(a, front, end);// 一次划分
        quickSort(a, front, pivot - 1);// 递归地对左侧子序列进行快速排序
        quickSort(a, pivot + 1, end);// 递归地对右侧子序列进行快速排序
    }
}

选择排序

简单选择排序(simple selction sort)

void selectSort(vector<int> &a) {
    for (int i = 0; i < a.size() - 1; i++) {// 对n个记录进行n-1躺简单选择排序
        int index = i;
        for (int j = i + 1; j < a.size(); j++) {// 在无序区中选取最小记录
            if (a[index] > a[j]) {
                index = j;
            }
        }
        if (index != i) {
            swap(a[i], a[index]);
        }
    }
}

堆排序(heap sort)

堆(heap) 完全二叉树(数组)

• 小根堆(结点<=左结点 && 结点<=右结点)
• 大根堆(结点>=左结点 && 结点>=右结点)

void sift(vector<int> &a, int front, int end) {
    int i = front, j = 2 * i + 1;// i指向被筛选结点,j指向结点i的左孩子
    while (j <= end) {// 筛选还没有进行到叶子
        if (j + 1 <= end && a[j + 1] > a[j]) {// 比较i的左右孩子,j指向较大者
            j++;
        }
        if (a[i] >= a[j]) {// 根结点已经大于左右孩子中的较大者
            break;
        } else {
            swap(a[i], a[j]);// 将根结点与结点j交换
            i = j; // 被筛结点位于原来结点j的位置
            j = 2 * i + 1;
        }
    }
}

void heapSort(vector<int> &a) {
    for (int i = a.size() / 2 - 1; i >= 0; i--) {// 初始建堆,从最后一个分支结点至根结点
        sift(a, i, a.size() - 1);
    }

    for (int i = 0; i < a.size(); i++) {// 重复执行移走堆顶及重建堆的操作
        swap(a[0], a[a.size() - 1 - i]);
        sift(a, 0, a.size() - 1 - i - 1);
    }
}

归并排序

二路归并排序

void merge(vector<int> &a, int front, int middle, int end) {
    int i = front, j = middle + 1;
    vector<int> b(end - front + 1);
    int k = 0;

    while (i <= middle && j <= end) {// 取a[i]和a[j]中的较小者放入b[k]
        if (a[i] <= a[j]) {
            b[k++] = a[i++];
        } else {
            b[k++] = a[j++];
        }
    }
    while (i <= middle) {// 若第一个子序列没处理完,则进行收尾处理
        b[k++] = a[i++];
    }
    while (j <= end) {// 若第二个子序列没处理完,则进行收尾处理
        b[k++] = a[j++];
    }

    for (int m = 0; m < k; m++) {
        a[front + m] = b[m];
    }
}

void mergeSort(vector<int> &a, int front, int end) {
    if (front < end) {
        int middle = (front + end) / 2;
        mergeSort(a, front, middle);// 归并排序前半个子序列
        mergeSort(a, middle + 1, end);// 归并排序后半个子序列
        merge(a, front, middle, end);// 将两个已排序的子序列归并
    }
}

---

排序

sort

对区间进行排序

bool cmp(int a, int b) {
    return a > b;
}

sort(a.begin(), a.end());
sort(a.begin(), a.end(), cmp);
sort(a.begin(), a.end(), less<>());
sort(a.begin(), a.end(), less_equal<>());
sort(a.begin(), a.end(), greater<>());
sort(a.begin(), a.end(), greater_equal<>());

stable_sort

对区间进行排序,并保留相同元素的相对顺序

• 归并排序

partial_sort

对区间进行部分排序,提供完整排序的前n个元素

• 堆排序

partial_sort(a.begin(), a.begin() + 5, a.end());