排序算法总结 - C++

冒泡排序: 主要原理是每次两两比较，大的往下沉。代码实现如下：

void BubbleSort(int array[], int len) {
    bool isSwap;
    for (int i = 0; i < len; i++) {
        isSwap = false;
        for (int j = 0; j < len - 1 - i; j++) {
            if (array[j] > array[j + 1]) {
                int temp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = temp;
                isSwap = true;
            }
        }
        if (!isSwap) {
            break;
        }
    }
}

选择排序：每一次从待排序的数据元素中选出最小的一个元素，存放在序列的起始位置，直到全部待排序的元素排完。代码实现如下：

void SelectionSort(int array[], int len) {
    int index;
    for (int i = 0; i < len - 1; i++) {
        index = i;
        for (int j = i + 1; j < len; j++) {
            if (array[index] > array[j]) {
                index = j;
            }
        }
        if (index != i) {
            int temp = array[i];
            array[i] = array[index];
            array[index] = temp;
        }
    }
}

插入排序：每步将一个待排序的记录，按其关键码的大小插入前面已经排序的队列适当位置上，直到全部插入完为止。代码实现如下：

void InsertSort(int array[], int len) {
    for (int i = 1; i < len; i++) {
        int temp = array[i];
        int j = i;
        while (array[j - 1] > temp && j > 0) {
            array[j] = array[j - 1];
            j--;
        }
        array[j] = temp;
    }
}

桶排序：简单的桶排序，适用于正整数且上界不大的数组排序。此处的映射直接是线性的。代码实现如下：

void BucketSort(int array[], int len) {
    int bucket[MAX];
    memset(bucket, 0, sizeof(bucket));

    for (int i = 0; i < len; i++) {
        bucket[array[i]]++;
    }

    int k = 0;
    for (int j = 0; j < MAX; j++) {
        while (bucket[j]--) {
            array[k++] = j;
        }
    }
}

快速排序：快速排序是找出一个元素（理论上可以随便找一个，一般都会选择第一个）作为基准（pivot），然后对数组进行分区操作，使基准左边的值都不大于基准值，其基准右边的元素值都不小于基准值，如此作为基准的元素调整到排序后的正确位置，递归快速排序，将其他n-1个元素也调整到排序后的正确位置。最后每个元素都是在排序后的正确位置，排序完成。所以快速排序算法的核心算法是分区操作，即如何调整基准的位置以及调整返回基准的最终位置以便分治递归。例如：
2 4 9 3 6 7 1 5 首先用 2 当作基准， 使用 i j 两个指针分别从两边进行扫描， 把比 2 小的元素和比 2 大的元素分开。 首先比较 2 和 5， 5 比 2 大， j 左移
2 4 9 3 6 7 1 5 比较 2 和 1， 1 小于 2， 所以把 1 放在 2 的位置
1 4 9 3 6 7 1 5 比较 2 和 4， 4 大于 2， 因此将 4 移动到后面
1 4 9 3 6 7 4 5 比较 2 和 7， 2 和 6， 2 和 3， 2 和 9， 全部大于 2， 满足件，因此不变
经过第一轮的快速排序， 元素变为下面的样子
[1] 2 [9 3 6 7 4 5]
代码实现如下：

void QuickSort(int array[], int left, int right) {
    if (left < right) {
        int key = array[left];
        int low = left;
        int high = right;
        while (low < high) {
            while (low < high && array[high] >= key) {
                high--;
            }
            array[low] = array[high];
            while (low < high && array[low] <= key) {
                low++;
            }
            array[high] = array[low];
        }

        array[low] = key;
        QuickSort(array, left, low - 1);
        QuickSort(array, low + 1, right);
    }
}