交换排序

C/C++ 评论

冒泡排序

从无序序列头部开始，进行两两比较，根据大小交换位置，直到最后将最大（小）的数据元素交换到了无序队列的队尾，从而成为有序序列的一部分；下一次继续这个过程，直到所有数据元素都排好序。算法的核心在于每次通过两两比较交换位置，选出剩余无序序列里最大（小）的数据元素放到队尾
时间复杂度：
最好：正序 比较次数n 移动次数0
最坏：反序 比较次数n2 移动次数n2
平均：O(n2)
空间复杂度：O(1)
稳定性：稳定

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void BubbleSort(int array[], int size) {
    for (int i = 0; i < size; i++) {
        int isSorted = 1;
        // 有序 [size - i, size - 1]
        // 无序 [0, size - 1 - i]
        for (int j = 0; j < size - 1 - i; j++) {
            if (array[j] > array[j + 1]) {
                swap(array[j], array[j + 1]);
                isSorted = 0;
            }
        }
        if (isSorted) {
            break;
        }
    }
}

优化

我们可以在每一轮排序的最后，记录下最后一次元素交换的位置，那个位置也就是无序数列的边界，再往后就是有序区了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void BubbleSort(int array[], int size) {
    for (int sortBorder = size; sortBorder > 1;) {
        int lastExchangeIndex = 0;
        // 无序 [0, sortBorder - 1]
        // 有序 [sortBorder, size - 1]
        for (int j = 0; j < sortBorder - 1; j++) {
            if (array[j] > array[j + 1]) {
                swap(array[j], array[j + 1]);
                lastExchangeIndex = j;
            }
        }
        sortBorder = lastExchangeIndex + 1;
    }
}

快速排序

通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列
每一层的Partition：
时间复杂度 O(n)
空间复杂度 O(1)
快速排序时间复杂度：
最好：T(n)=2T(n/2)+O(n)=>T(n)=O(n  log n)T(n)=2T(n/2)+O(n)=>T(n)=O(n\;log\,n)
最坏：T(n)=T(n−1)+O(n)=>T(n)=O(n2)T(n)=T(n-1)+O(n)=>T(n)=O(n^2)
平均：T(n)=1n∑k=1n(T(n−k)+T(k−1))+n=2n∑k=1nT(k)+n=>T(n)=O(n  log n)T(n)=\frac1{n}\sum_{k=1}^n(T(n-k)+T(k-1))+n=\frac2{n}\sum_{k=1}^nT(k)+n=>T(n)=O(n\;log\,n)
快速排序空间复杂度：
空间消耗在于递归调用的栈帧消耗，最终消耗的情况是二叉树的高度，二叉树的高度在log(n) ~ n变化
最好：O(log n)
最坏：O(n)
平均：O(log n)
稳定性：不稳定

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
// Hover
int Partition_1(int array[], int left, int right) {
    int begin = left;    // [left, begin] 保证 <= pivot
    int end = right - 1; // [end, right]  保证 >= pivot
    int pivot = array[right]; // 基准值
    while (begin < end) {
        while (begin < end && array[begin] <= pivot) {
            begin++;
        }
        while (begin < end && array[end] >= pivot) {
            end--;
        }
        swap(array[begin], array[end]);
    }
    // 把基准值和begin所在的下标交换，和第一个比pivot大的数交换
    swap(array[begin], array[right]);
    return begin;
}

// 挖坑
int Partition_2(int array[], int left, int right) {
    int begin = left; // [left, begin] 保证 <= pivot
    int end = right;  // [end, right]  保证 >= pivot
    int pivot = array[right]; // 基准值
    while (begin < end) {
        while (begin < end && array[begin] <= pivot) {
            begin++;
        }
        array[end] = array[begin];
        while (begin < end && array[end] >= pivot) {
            end--;
        }
        array[begin] = array[end];
    }
    array[begin] = pivot;
    return begin;
}

// 前后下标
int Partition_3(int array[], int left, int right) {
    int d = left;
    for (int i = left; i < right; i++) {
        if (array[i] < array[right]) {
            swap(array[i], array[d]);
            d++;
        }
    }
    swap(array[d], array[right]);
    return d;
}

void QuickSortInner(int array[], int left, int right) {
    if (left >= right) {
        // size <= 1
        return;
    }
    // 1. 确定基准值
    // 2. 遍历区间，进行切割，直到小的全在左，大的全在右，并且返回最终基准值所在的下标
    int d = Partition_1(array, left, right);
    // [left, right]  的区间被分成三部分
    // [left, d - 1]  <= pivot
    // [d]            == pivot
    // [d + 1, right] >= pivot
    // 3. 分治处理所有两个小区间
    QuickSortInner(array, left, d - 1);
    QuickSortInner(array, d + 1, right);
}

void QuickSort(int array[], int size) {
    QuickSortInner(array, 0, size - 1);
}

void QuickSortNoR(int array[], int size) {
    // 保存要排序区间的左右边界
    std::stack<int>	stack;
    stack.push(size - 1); // right
    stack.push(0);        // left
    while (!stack.empty()) {
        int left = stack.top();
        stack.pop();
        int right = stack.top();
        stack.pop();
        if (left >= right) {
            continue;
        }
        int d = Partition_1(array, left, right);
        // [d + 1, right]
        stack.push(right);
        stack.push(d + 1);
        // [left, d - 1]
        stack.push(d - 1);
        stack.push(left);
    }
}

优化

  1. 上面的版本我们选择array[right]作为基准值，这其实是一种很不聪明的取法，当初始序列一开始就是有序的，则快速排序时间复杂度为T(n)=T(n−1)+O(n)=O(n2)T(n)=T(n-1)+O(n)=O(n^2)所以pivot最好用三数取中法来选取
  2. Partition函数中，如果有元素正好等于pivot，最好停下来做交换，虽然这样做了很多无谓的交换，但是最后i和j会停在比较中间的位置，主元也会被换在在比较中间的位置，这样做每一次递归的时候，原始序列基本被等分成两个等长的序列这样时间复杂度为O(n * log n)；如果不停下来交换而继续移动指针，这样其中一个指针是不动的，导致主元被放在一个端点，这样就成了O(n2)复杂度的算法了
  3. 对于大规模数据我们用递归，而对于递归的数据规模充分的小的时候则停止递归，直接调用简单排序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#define CUTOFF 7 // 数组长度阈值

int Median3(int array[], int left, int right) {
    int center = (left + right) / 2;
    if (array[left] > array[center]) {
        swap(array[left], array[center]);
    }
    if (array[left] > array[right]) {
        swap(array[left], array[right]);
    }
    if (array[center] > array[right]) {
        swap(array[center], array[right]);
    }
    // 此时A[left] <= A[center] <= A[right]
    swap(array[center], array[right - 1]); // 将基准pivot藏到右边
    // 只需要考虑A[left + 1] … A[right - 2]
    return  array[right - 1];  // 返回基准Pivot
}

int Partition(int array[], int left, int right) {
    int pivot = Median3(array, left, right); // 基准值
    // 只需要考虑A[left + 1] … A[right - 2]
    int begin = left + 1; // [left, begin] 保证 <= pivot
    int end = right - 2;  // [end, right]  保证 >= pivot
     while (begin < end) {
        while (begin < end && array[begin] < pivot) {
            begin++;
        }
        while (begin < end && array[end] > pivot) {
            end--;
        }
        swap(array[begin], array[end]);
    }
    // 把基准值和begin所在的下标交换，和第一个比pivot大的数交换
    swap(array[begin], array[right]);
    return begin;
}

void QuickSortInner(int array[], int left, int right) {
    if ((right - left) > CUTOFF) {
        // 调用快速排序
        // 1. 确定基准值
        // 2. 遍历区间，进行切割，直到小的全在左，大的全在右，并且返回最终基准值所在的下标
        int d = Partition_1(array, left, right);
        // [left, right]  的区间被分成三部分
        // [left, d - 1]  <= pivot
        // [d]            == pivot
        // [d + 1, right] >= pivot
        // 3. 分治处理所有两个小区间
        QuickSortInner(array, left, d - 1);
        QuickSortInner(array, d + 1, right);
    } else {
        InsertSort(array + left, right - left + 1);
    }
}

RanI am a student

stay healthy and happy