文章目录

• 1 冒泡排序
• • 1.1 思路
  • 1.2 算法时间复杂度与稳定性
  • 1.3 代码示例
• 2 简单选择排序
• • 2.1 思路
  • 2.2 算法时间复杂度与稳定性
  • 2.3 代码示例
• 3 直接插入排序
• • 3.1 思路
  • 3.2 算法时间复杂度与稳定性
  • 3.3 代码示例
• 4 归并排序
• • 4.1 思路
  • 4.2 算法时间复杂度与稳定性
  • 4.3 代码示例
• 5 快速排序
• • 5.1 思路
  • 5.2 算法时间复杂度与稳定性
  • 5.3 代码示例
• 6 桶排序—计数排序
• • 6.1 思路
  • 6.2 算法时间复杂度与稳定性
  • 6.3 代码示例
• 综合源码

前言

1. 这里简单介绍几个常用的排序算法的基本原理以及手写源码。
2. 虽然各类语言的标准库基本上都集成了排序算法，但是遇到复杂的业务需求还是需要结合自身需求完成手写工作。
3. Default：升序排序，数据为整数。

1 冒泡排序

1.1 思路

• 最基本的一类交换排序，从前往后两两比较相邻元素，若逆序则交换，这样视为一趟排序，每一趟的结果是将最大的元素交换到待排序列的最后一个位置；
• 前一趟确定的最大元素不需要参与当前趟，最多做 N-1 趟即可完成排序。
• 中间若遇到已经排序完毕的情况则可直接退出，故适合基本有序的序列。

1.2 算法时间复杂度与稳定性

• O(N2)O(N^2)O(N2)
• 稳定

1.3 代码示例

void SortUtil::bubbleSort() {bool isSwap = false;for (int i = 0; i < len - 1; i++)    // i:排序趟次{for (int j = 0; j < len - i - 1; j++)    // j：每轮排序的比较次数{if (this->data[j + 1] < this->data[j])  // 升序{swap(data[j], data[j + 1]);isSwap = true;}}if (!isSwap) {break;}}
}

2 简单选择排序

2.1 思路

• 设待排数组为data[1…N]，第i次排序遍历[i…N]并从中选出最小的元素与data[i]交换，视为一趟排序。
• 每一趟排序都能确定元素data[i]已经是最终位置。
• 备注：除此之外，堆排序是一种复杂的选择排序

2.2 算法时间复杂度与稳定性

• O(N2)O(N^2)O(N2)
• 不稳定

2.3 代码示例

void SortUtil::selectionSort() {int minIndex = 0;for (int i = 0; i < len - 1; i++) {minIndex = i;for (int j = i + 1; j < len; j++) {if (data[j] < data[minIndex]) minIndex = j;}swap(data[i], data[minIndex]);}
}

3 直接插入排序

3.1 思路

• 设待排数组为data[1...N]，假设在某一趟排序中，data[1...i-1]已经有序，则遍历data[1...i-1]并与data[i]的大小做比较，从而将data[i]插入使得data[1...i]有序，视为一趟排序。
• 每一趟排序都能保证其前缀数组是有序的，直到整个数组有序。
• 备注：除此之外，在其基础上还有折半插入排序、希尔排序等）

3.2 算法时间复杂度与稳定性

• O(N2)O(N^2)O(N2)
• 稳定

3.3 代码示例

void SortUtil::insertionSort() {for (int i = 0; i < len; i++) {for (int j = i; j > 0; j--) {if (data[j] < data[j - 1]) swap(data[j], data[j - 1]); // 维持下标为0->j的局部数组有序else break;}}
}

4 归并排序

4.1 思路

• 基于分治法，将一个完整的数组看成若干个有序数组构成的线性表，这若干个有序数组称之为若干个归并段（初始归并段长度为一），每一趟排序都依次将相邻的两个归并段看成一组（即 2 路归并，同理可有 3 路、4 路），将该组归并段合并产生一个更大的归并段。
• log2Nlog_2Nlog2​N 趟排序后，完整数组就成功归并为单个归并段了，排序工作完成。（本代码示例使用递归方法完成归并段的分段和归并）

4.2 算法时间复杂度与稳定性

• O(N∗logN)O(N*logN)O(N∗logN)
• 稳定

4.3 代码示例

void SortUtil::mergeSort() {recursiveMergeSort(0, len - 1);
}void SortUtil::recursiveMergeSort(int low, int high) {if (low < high) {// divideint mid = (low + high) / 2;recursiveMergeSort(low, mid);recursiveMergeSort(mid + 1, high);// mergevector data_B(data); // 辅助数组int i, j, k;for (i = low, j = mid + 1, k = low; i <= mid && j <= high; k++) {// 从data_B的左右两段中找较小值复制进dataif (data_B[i] <= data_B[j]) data[k] = data_B[i++];else data[k] = data_B[j++];}// 未检测的一段while (i <= mid) data[k++] = data_B[i++];while (j <= high) data[k++] = data_B[j++];}
}

5 快速排序

5.1 思路

• 基于分治法，每一趟排序都在选中的数组范围内产生一个枢纽，枢纽左侧的元素皆小于枢纽，右侧反之，即每一趟排序都将待排数组划分为独立的两个部分。
• 接下来分而治之，递归地对这两个部分都重复上述排序，直到最后整个数组有序。

5.2 算法时间复杂度与稳定性

• 一般稳定在O(N∗logN)O(N*logN)O(N∗logN)
• 不稳定

5.3 代码示例

void SortUtil::quickSort() {recursiveQuickSort(0, len - 1);
}void SortUtil::recursiveQuickSort(int low, int high) {if (low < high) {// 划分左右，产生枢纽位置下标midIndint midInd = getPartition(low, high);// 左右分治，递归recursiveQuickSort(low, midInd - 1);recursiveQuickSort(midInd + 1, high);}
}int SortUtil::getPartition(int low, int high) {int midVal = data[low]; // 划分枢纽值初始化为数组在该范围内的第一个元素while (low < high) {// 从右边找第一个小于枢纽值的数，复制至左边while (low < high && data[high] >= midVal) high--;data[low] = data[high];// 从左边找第一个大于枢纽值的数，复制至右边while (low < high && data[low] <= midVal) low++;data[high] = data[low];}data[low] = midVal; // 枢纽元素归位至最终位置return low; // 枢纽的最终位置（此时枢纽左边的数皆小于midVal，右边的皆大于midVal，一次划分结束）
}

6 桶排序—计数排序

6.1 思路

• 桶排序的一种特定排序方案，桶内不安排排序而是存放一个数的出现次数（即计数），通过映射来取代比较，从而直接遍历桶来产生有序序列

6.2 算法时间复杂度与稳定性

• O(N)O(N)O(N)，要求数据的数值范围较小
• 可通过优化达到稳定

6.3 代码示例

void SortUtil::countingSort(int maxNum) {vector count(maxNum, 0);  // 开辟maxNum个桶，maxNum为数据中的最大数值（暂不考虑负数情况）for (int i = 0; i < len; i++) {if (data[i] < 0) {cout << "负数" << endl;break;}count[data[i]]++;}data.resize(0);for(int i=0;iif(count[i]!=0){  // 若存在计数，则向data插入若干个数，个数由计数值决定fill_n(back_inserter(data),count[i],i);}}
}

综合源码

//
// Created by retro on 2023/2/8.
//
/**
* 请用C++代码实现3-5种不同的排序算法程序。其中算法的时间复杂度至少有一种是N的平方，一种是N*logN，一种是N。
*/
#include 
#include using namespace std;/*** 提供常见的排序算法* default：升序排序，数据为整数*/
class SortUtil {
public:vector data;int len;void init();void printData();void bubbleSort();  // 冒泡排序void selectionSort();  // 简单选择排序void insertionSort();  // 直接插入排序void mergeSort();  // 归并排序void quickSort();  // 快速排序void countingSort(int maxNum);  // 桶排序-计数排序private:void recursiveMergeSort(int low, int high);   // 归并排序的递归函数void recursiveQuickSort(int low, int high);    // 快速排序的递归函数int getPartition(int low, int high); // 用于实现快速排序的划分，返回枢纽位置};/*** 初始化输入数组* 首先输入数组大小，再输入一组数据，中间用空格隔开* e.g. 8 6 8 7 5 3 1 2 4  (means input [6 8 7 5 3 1 2 4])*/
void SortUtil::init() {cin >> this->len;this->data.resize(len, 0);for (int i = 0; i < len; i++) {cin >> this->data[i];}
}/***  打印当前数组，用于测试*/
void SortUtil::printData() {cout << "data size = " << this->len << endl;for (int i = 0; i < this->len; i++) {cout << data[i] << (i == this->len - 1 ? "\n" : " ");}cout << "---------------------" << endl;
}/*** 0.冒泡排序（稳定）* 思路：最基本的一类交换排序，从前往后两两比较相邻元素，若逆序则交换，这样视为一趟排序，每一趟的结果是将最大的元素交换到待排序列的最后一个位置；*      前一趟确定的最大元素不需要参与当前趟，最多做N-1趟即可完成排序。*      中间若遇到已经排序完毕的情况则可直接退出，故适合基本有序的序列。* 算法时间复杂度：O(N^2)*/
void SortUtil::bubbleSort() {bool isSwap = false;for (int i = 0; i < len - 1; i++)    // i:排序趟次{for (int j = 0; j < len - i - 1; j++)    // j：每轮排序的比较次数{if (this->data[j + 1] < this->data[j])  // 升序{swap(data[j], data[j + 1]);isSwap = true;}}if (!isSwap) {break;}}
}/*** 1.简单选择排序（不稳定）（除此之外，堆排序是一种复杂的选择排序）* 思路：设待排数组为data[1...N]，第i次排序遍历[i...N]并从中选出最小的元素与data[i]交换，视为一趟排序。*      每一趟排序都能确定元素data[i]已经是最终位置。* 算法时间复杂度：O(N^2)*/
void SortUtil::selectionSort() {int minIndex = 0;for (int i = 0; i < len - 1; i++) {minIndex = i;for (int j = i + 1; j < len; j++) {if (data[j] < data[minIndex]) minIndex = j;}swap(data[i], data[minIndex]);}
}/*** 2.直接插入排序（稳定）（除此之外，在其基础上还有折半插入排序、希尔排序等）* 思路：设待排数组为data[1...N]，假设在某一趟排序中，data[1...i-1]已经有序，则遍历data[1...i-1]并与data[i]的大小做比较，从而将data[i]插入使得data[1...i]有序，视为一趟排序。*      每一趟排序都能保证其前缀数组是有序的，直到整个数组有序。* 算法时间复杂度：O(N^2)**/
void SortUtil::insertionSort() {for (int i = 0; i < len; i++) {for (int j = i; j > 0; j--) {if (data[j] < data[j - 1]) swap(data[j], data[j - 1]); // 维持下标为0->j的局部数组有序else break;}}
}/*** 3.归并排序（稳定）* 思路：基于分治法，将一个完整的数组看成若干个有序数组构成的线性表，这若干个有序数组称之为若干个归并段（初始归并段长度为一），每一趟排序都依次将相邻的两个归并段看成一组（即2路归并，同理可有3路、4路），将该组归并段合并产生一个更大的归并段。*      log2N趟排序后，完整数组就成功归并为单个归并段了，排序工作完成。（本代码示例使用递归方法完成归并段的分段和归并）* 算法时间复杂度：O(N*logN)*/
void SortUtil::mergeSort() {recursiveMergeSort(0, len - 1);
}void SortUtil::recursiveMergeSort(int low, int high) {if (low < high) {// divideint mid = (low + high) / 2;recursiveMergeSort(low, mid);recursiveMergeSort(mid + 1, high);// mergevector data_B(data); // 辅助数组int i, j, k;for (i = low, j = mid + 1, k = low; i <= mid && j <= high; k++) {// 从data_B的左右两段中找较小值复制进dataif (data_B[i] <= data_B[j]) data[k] = data_B[i++];else data[k] = data_B[j++];}// 未检测的一段while (i <= mid) data[k++] = data_B[i++];while (j <= high) data[k++] = data_B[j++];}
}/***  4.快速排序（不稳定）*  思路：基于分治法，每一趟排序都在选中的数组范围内产生一个枢纽，枢纽左侧的元素皆小于枢纽，右侧反之，即每一趟排序都将待排数组划分为独立的两个部分。*       接下来分而治之，递归地对这两个部分都重复上述排序，直到最后整个数组有序。*  算法时间复杂度：一般稳定在O(N*logN)*/
void SortUtil::quickSort() {recursiveQuickSort(0, len - 1);
}void SortUtil::recursiveQuickSort(int low, int high) {if (low < high) {// 划分左右，产生枢纽位置下标midIndint midInd = getPartition(low, high);// 左右分治，递归recursiveQuickSort(low, midInd - 1);recursiveQuickSort(midInd + 1, high);}
}int SortUtil::getPartition(int low, int high) {int midVal = data[low]; // 划分枢纽值初始化为数组在该范围内的第一个元素while (low < high) {// 从右边找第一个小于枢纽值的数，复制至左边while (low < high && data[high] >= midVal) high--;data[low] = data[high];// 从左边找第一个大于枢纽值的数，复制至右边while (low < high && data[low] <= midVal) low++;data[high] = data[low];}data[low] = midVal; // 枢纽元素归位至最终位置return low; // 枢纽的最终位置（此时枢纽左边的数皆小于midVal，右边的皆大于midVal，一次划分结束）
}/*** 5.桶排序-计数排序* 思路：桶排序的一种特定排序方案，桶内不安排排序而是存放一个数的出现次数（即计数），通过映射来取代比较，从而直接遍历桶来产生有序序列* 算法时间复杂度：O(N)，要求数据的数值范围较小*/
void SortUtil::countingSort(int maxNum) {vector count(maxNum, 0);  // 开辟maxNum个桶，maxNum为数据中的最大数值（暂不考虑负数情况）for (int i = 0; i < len; i++) {if (data[i] < 0) {cout << "负数" << endl;break;}count[data[i]]++;}data.resize(0);for(int i=0;iif(count[i]!=0){  // 若存在计数，则向data插入若干个数，个数由计数值决定fill_n(back_inserter(data),count[i],i);}}
}int main() {SortUtil sortUtil;sortUtil.init();sortUtil.len = sortUtil.data.size();cout << "before:" << endl;sortUtil.printData();sortUtil.bubbleSort();sortUtil.selectionSort();sortUtil.insertionSort();sortUtil.mergeSort();sortUtil.quickSort();sortUtil.countingSort(10000);cout << "after:" << endl;sortUtil.printData();return 0;
}