sorting algorithms

冒泡排序

排序算法

冒泡排序

适用场景：数据量小，基本有序，稳定

步骤：

1. 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
2. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
3. 针对所有的元素重复以上的步骤，除了最后一个。
4. 重复步骤1~3，直到排序完成。

int main() {
    int arr[] = {6, 1, 5, 2, 4, 3};
    int len = sizeof(arr) / sizeof(arr[0]);
    for (int i = 0; i < len; ++i) {
        for (int j = 0; j < len - i - 1; ++j) {
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
    for (int i = 0; i < len; ++i) {
        cout << arr[i] << " ";
    }

    return 0;
}

选择排序

适用场景：数据量小，基本有序，不稳定

选择排序的不稳定性体现在：当有多个相同的元素时，选择排序会交换相同元素的位置，从而导致相同元素的前后顺序发生变化。

步骤：

1. 首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置
2. 再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
3. 重复第二步，直到所有元素均排序完毕。

int main() {
    int arr[] = {6, 1, 5, 2, 4, 3};
    int len = sizeof(arr) / sizeof(arr[0]);
    for (int i = 0; i < len; ++i) {
        int min = i;
        for (int j = i + 1; j < len; ++j) {
            if (arr[j] < arr[min]) {
                min = j;
            }
        }
        if (min != i) {
            int temp = arr[i];
            arr[i] = arr[min];
            arr[min] = temp;
        }
    }
    for (int i = 0; i < len; ++i) {
        cout << arr[i] << " ";
    }

    return 0;
}

插入排序

适用场景：数据量小，基本有序，稳定

步骤：

1. 从第一个元素开始，该元素可以认为已经被排序
2. 取出下一个元素，在已经排序的元素序列中从后向前扫描
3. 如果该元素（已排序）大于新元素，将该元素移到下一位置
4. 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
5. 将新元素插入到该位置后
6. 重复步骤2~5

int main() {
    int arr[] = {6, 1, 5, 2, 4, 3};
    int len = sizeof(arr) / sizeof(arr[0]);
    for (int i = 1; i < len; ++i) {
        int temp = arr[i];
        int j = i - 1;
        while (j >= 0 && arr[j] > temp) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = temp;
    }
    for (int i = 0; i < len; ++i) {
        cout << arr[i] << " ";
    }
    return 0;
}

希尔排序

适用场景：数据量大，基本无序，不稳定

希尔排序的不稳定性体现在：当增量序列的最后一个增量为1时，希尔排序退化为直接插入排序，此时希尔排序就不稳定了。

步骤：

1. 选择一个增量序列 t1，t2，…，tk，其中 ti > tj, tk = 1
2. 按增量序列个数 k，对序列进行 k 趟排序
3. 每趟排序，根据对应的增量 ti，将待排序列分割成若干长度为 m 的子序列，分别对各子表进行直接插入排序。仅增量因子为 1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

int main() {
    int arr[] = {6, 1, 5, 2, 4, 3};
    int len = sizeof(arr) / sizeof(arr[0]);
    int gap = len / 2; // 初始增量, len/2=3 意味着数组被分为了 3 组,每组2个, 对这3 组分别进行插入排序
    while (gap > 0) {   
        for (int i = gap; i < len; ++i) {
            int temp = arr[i];
            int j = i - gap;
            while (j >= 0 && arr[j] > temp) {
                arr[j + gap] = arr[j];
                j -= gap;
            }
            arr[j + gap] = temp;
        }
        gap /= 2; // 缩小增量, 如len/4=1 意味着数组被分为了 6 组,每组1个, 对这6 组分别进行插入排序
    }
    for (int i = 0; i < len; ++i) {
        cout << arr[i] << " ";
    }
    return 0;
}

归并排序

适用场景：数据量大，基本无序，稳定

步骤：

1. 把长度为 n 的输入序列分成两个长度为 n/2 的子序列
2. 对这两个子序列分别采用归并排序
3. 将两个排序好的子序列合并成一个最终的排序序列

//将两个有序数组合并成一个有序数组, 且合并后的数组长度为 len1+len2
void merge(int arr[], int left, int mid, int right) {
    int i = left;
    int j = mid + 1;
    int k = 0; // 临时数组的下标
    int temp[right - left + 1];
    while (i <= mid && j <= right) { 
        if (arr[i] <= arr[j]) { 
            temp[k++] = arr[i++];
        } else {
            temp[k++] = arr[j++];
        }
    }
    while (i <= mid) { // 将左边剩余元素填充进temp中
        temp[k++] = arr[i++];
    }
    while (j <= right) { // 将右序列剩余元素填充进temp中
        temp[k++] = arr[j++];
    }
    for (int i = 0; i < k; ++i) { // 将temp中的元素全部拷贝到原数组中
        arr[left + i] = temp[i];
    }
}

void mergeSort(int arr[], int left, int right) {
    if (left < right) {
        int mid = (left + right) / 2;
        mergeSort(arr, left, mid); // 左边归并排序，使得左子序列有序
        mergeSort(arr, mid + 1, right); // 右边归并排序，使得右子序列有序
        merge(arr, left, mid, right); // 将两个有序子数组合并操作
    }
    // 递归的终止条件是 left == right
}

int main() {
    int arr[] = {6, 1, 5, 2, 4, 3};
    int len = sizeof(arr) / sizeof(arr[0]);
    mergeSort(arr, 0, len - 1);
    for (int i = 0; i < len; ++i) {
        cout << arr[i] << " ";
    }
    return 0;
}

快速排序

适用场景：数据量大，基本无序，不稳定

快速排序的不稳定性体现在：当待排序的序列中存在大量重复的元素时，快速排序的性能会急剧下降，此时快速排序就不稳定了。

步骤：

1. 从数列中挑出一个元素，称为 “基准”（pivot）;
2. 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。
3. 在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。
4. 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。

int partition(int arr[], int left, int right) {
    int pivot = arr[left]; // 选取第一个元素作为基准
    while (left < right) {
        while (left < right && arr[right] >= pivot) {
            right--;
        }
        arr[left] = arr[right];
        while (left < right && arr[left] <= pivot) {
            left++;
        }
        arr[right] = arr[left];
    }
    arr[left] = pivot;
    return left;
}

void quickSort(int arr[], int left, int right) {
    if (left < right) {
        int pivot = partition(arr, left, right);
        quickSort(arr, left, pivot - 1);
        quickSort(arr, pivot + 1, right);
    }
}

int main() {
    int arr[] = {6, 1, 5, 2, 4, 3};
    int len = sizeof(arr) / sizeof(arr[0]);
    quickSort(arr, 0, len - 1);
    for (int i = 0; i < len; ++i) {
        cout << arr[i] << " ";
    }
    return 0;
}

堆排序

适用场景：数据量大，基本无序，不稳定

堆排序的不稳定性体现在：当待排序的序列中存在大量重复的元素时，堆排序的性能会急剧下降，此时堆排序就不稳定了。

步骤：

1. 构建一个大顶堆（或小顶堆）。
2. 将堆顶元素与末尾元素交换，将最大元素“沉”到数组末端。
3. 重新调整结构，使其满足堆定义，然后继续交换堆顶元素与当前末尾元素，反复执行调整+交换步骤，直到整个序列有序。

void heapify(int arr[], int n, int i) {
    if (i >= n) {
        return;
    }
    int c1 = 2 * i + 1;
    int c2 = 2 * i + 2;
    int max = i;
    if (c1 < n && arr[c1] > arr[max]) {
        max = c1;
    }
    if (c2 < n && arr[c2] > arr[max]) {
        max = c2;
    }
    if (max != i) {
        swap(arr[i], arr[max]);
        heapify(arr, n, max);
    }
}

void buildHeap(int arr[], int n) {
    int lastNode = n - 1;
    int parent = (lastNode - 1) / 2;
    for (int i = parent; i >= 0; --i) {
        heapify(arr, n, i);
    }
}

void heapSort(int arr[], int n) {
    buildHeap(arr, n);
    for (int i = n - 1; i >= 0; --i) {
        swap(arr[0], arr[i]);
        heapify(arr, i, 0);
    }
}

int main() {
    int arr[] = {6, 1, 5, 2, 4, 3};
    int len = sizeof(arr) / sizeof(arr[0]);
    heapSort(arr, len);
    for (int i = 0; i < len; ++i) {
        cout << arr[i] << " ";
    }
    return 0;
}

计数排序

适用场景：数据量大，基本有序，稳定

步骤：

1. 找出待排序的数组中最大和最小的元素；
2. 统计数组中每个值为i的元素出现的次数，存入数组C的第i项；
3. 对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）；
4. 反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1。

void countSort(int arr[], int n) {
    int max = arr[0];
    int min = arr[0];
    for (int i = 1; i < n; ++i) {
        if (arr[i] > max) {
            max = arr[i];
        }
        if (arr[i] < min) {
            min = arr[i];
        }
    }
    int range = max - min + 1;
    int *countArr = new int[range];
    memset(countArr, 0, range * sizeof(int));
    for (int i = 0; i < n; ++i) {
        countArr[arr[i] - min]++;
    }
    for (int i = 1; i < range; ++i) {
        countArr[i] += countArr[i - 1];
    }
    int *sortedArr = new int[n];
    for (int i = n - 1; i >= 0; --i) {
        sortedArr[countArr[arr[i] - min] - 1] = arr[i];
        countArr[arr[i] - min]--;
    }
    for (int i = 0; i < n; ++i) {
        arr[i] = sortedArr[i];
    }
    delete[] countArr;
    delete[] sortedArr;
}

int main() {
    int arr[] = {6, 1, 5, 2, 4, 3};
    int len = sizeof(arr) / sizeof(arr[0]);
    countSort(arr, len);
    for (int i = 0; i < len; ++i) {
        cout << arr[i] << " ";
    }
    return 0;
}

桶排序

适用场景：数据量大，基本有序，稳定

步骤：

1. 设置固定数量的空桶；
2. 把数据放入对应的桶中；
3. 对每个桶中的数据进行排序；
4. 拼接所有桶中的数据。

void bucketSort(int arr[], int n) {
    int max = arr[0];
    int min = arr[0];
    for (int i = 1; i < n; ++i) {
        if (arr[i] > max) {
            max = arr[i];
        }
        if (arr[i] < min) {
            min = arr[i];
        }
    }
    int bucketNum = (max - min) / n + 1;
    vector<vector<int>> buckets(bucketNum);
    for (int i = 0; i < n; ++i) {
        int index = (arr[i] - min) / n;
        buckets[index].push_back(arr[i]);
    }
    for (int i = 0; i < bucketNum; ++i) {
        sort(buckets[i].begin(), buckets[i].end());
    }
    int index = 0;
    for (int i = 0; i < bucketNum; ++i) {
        for (int j = 0; j < buckets[i].size(); ++j) {
            arr[index++] = buckets[i][j];
        }
    }
}

int main() {
    int arr[] = {6, 1, 5, 2, 4, 3};
    int len = sizeof(arr) / sizeof(arr[0]);
    bucketSort(arr, len);
    for (int i = 0; i < len; ++i) {
        cout << arr[i] << " ";
    }
    return 0;
}

基数排序

适用场景：数据量大，基本有序，稳定

步骤：

1. 取得数组中的最大数，并取得位数；
2. arr为原始数组，从最低位开始取每个位组成radix数组；
3. 对radix进行计数排序（利用计数排序适用于小范围数的特点）；

void radixSort(int arr[], int n) {
    int max = arr[0];
    for (int i = 1; i < n; ++i) {
        if (arr[i] > max) {
            max = arr[i]; 
        }
    }
    int maxDigit = 0;
    while (max != 0) {
        max /= 10;
        maxDigit++;
    }
    int mod = 10;
    int dev = 1;
    vector<vector<int>> counter(10);
    for (int i = 0; i < maxDigit; ++i, mod *= 10, dev *= 10) {
        for (int j = 0; j < n; ++j) {
            int bucket = arr[j] % mod / dev;
            counter[bucket].push_back(arr[j]);
        }
        int index = 0;
        for (int j = 0; j < 10; ++j) {
            for (int k = 0; k < counter[j].size(); ++k) {
                arr[index++] = counter[j][k];
            }
            counter[j].clear();
        }
    }
}

int main() {
    int arr[] = {6, 1, 5, 2, 4, 3};
    int len = sizeof(arr) / sizeof(arr[0]);
    radixSort(arr, len);
    for (int i = 0; i < len; ++i) {
        cout << arr[i] << " ";
    }
    return 0;
}

总结

排序算法的稳定性是指：如果待排序的序列中存在值相等的元素，经过排序之后，相等元素之间原有的先后顺序不变。

各个算法的复杂度