基础排序
关键词说明：
稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。
冒泡排序
从数组中第一个数开始，依次遍历数组中的每一个数，通过相邻比较交换，每一轮循环下来找出剩余未排序数的中的最大数并“冒泡”至数列的顶端。
稳定性：稳定
平均时间复杂度：$$O(n^2)$$
C++实现：
/**
* @brief 冒泡排序
* 比较相邻的元素。如果第一个比第二个大，就交换它们两个；
* 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；
* 针对所有的元素重复以上的步骤，除了最后一个；
* 重复步骤1~3，直到排序完成。
* @param arr
*/
void bubbleSort(vector<int>& arr) {
bool swap_ = false;
for (int i = arr.size() - 1; i > 0; --i) {
swap_ = false;
for (int j = 0; j < i; j++) {
if (arr[j] > arr[j + 1]) { // 如果相邻的元素前面比较大，就需要交换
swap(arr[j], arr[j + 1]);
swap_ = true;
}
} //end loop j
if (!swap_) break; // 当前一轮没有进行交换时，说明数组已经有序，没有必要再进行下一轮的循环了
} // end loop i
}插入排序
从待排序的n个记录中的第二个记录开始，依次与前面的记录比较并寻找插入的位置，每次外循环结束后，将当前的数插入到合适的位置。
稳定性：稳定
平均时间复杂度：$$O(n^2)$$
/**
* @brief 插入排序
* 插入排序是一种简单直观的排序算法。
* 它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
* 1、 把待排序的数组分成已排序和未排序两部分，初始的时候把第一个元素认为是已排好序的。
* 2、 从第二个元素开始，在已排好序的子数组中寻找到该元素合适的位置并插入该位置。
* 3、 重复上述过程直到最后一个元素被插入有序子数组中。
* @param arr
*/
void insertSort(vector<int>& arr) {
int value_ = 0;
if (arr.empty() || arr.size() == 1) return;
for (int i = 1; i < arr.size(); ++i) { // 从第二个元素开始
value_ = arr[i]; // 先记录一下这个元素
int pos = i;
while (pos > 0 && arr[pos - 1] > value_) {
arr[pos] = arr[pos - 1];
pos--;
}
// 从后往前找到value_的位置pos
arr[pos] = value_;
}
}选择排序
从所有记录中选出最小的一个数据元素与第一个位置的记录交换；然后在剩下的记录当中再找最小的与第二个位置的记录交换，循环到只剩下最后一个数据元素为止。
稳定性：不稳定
平均时间复杂度：$$O(n^2)$$
/**
* @brief 选择排序
* 是一种交换排序算法，是冒泡的一种改进
* 1、在未排序序列中找到最小（大）元素，存放到排序序列的起始位置
* 2、从剩余未排序元素中继续寻找，然后放到已经排序序列的末尾
* 3、重复第二步直至所有元素排列完毕
* 注意：这里只需要记录下标，最后再交换
* @param arr
*/
void selectionSort(vector<int>& arr) {
int min_ = 0;
for (int i = 0; i < arr.size() - 1; ++i) {
min_ = i;
for (int j = i + 1; j < arr.size(); ++j) {
if (arr[min_] > arr[j]) { // 找到后面更小的元素就记录一下
min_ = j;
}
}
if (min_ != i) {
swap(arr[i], arr[min_]);
}
}
}希尔排序（缩小增量排序）
希尔排序法是对相邻指定距离(称为增量)的元素进行比较，并不断把增量缩小至1，完成排序。
希尔排序开始时增量较大，分组较多，每组的记录数目较少，故在各组内采用直接插入排序较快，后来增量di逐渐缩小，分组数减少，各组的记录数增多，但由于已经按di−1分组排序，文件叫接近于有序状态，所以新的一趟排序过程较快。因此希尔 排序在效率上比直接插入排序有较大的改进。
在直接插入排序的基础上，将直接插入排序中的1全部改变成增量d即可，因为希尔排序最后一轮的增量d就为1。
稳定性：不稳定
平均时间复杂度：希尔排序算法的时间复杂度分析比较复杂，实际所需的时间取决于各次排序时增量的个数和增量的取值。时间复杂度在O(n^1.3)到O(n^2)之间。
快速排序(重要)
1）从待排序的n个记录中任意选取一个记录（通常选取第一个记录）为分区标准，称为pivot;
2）把所有小于该排序列的记录移动到左边，把所有大于该排序码的记录移动到右边，中间放所选记录，称之为第一趟排序；
3）然后对前后两个子序列分别重复上述过程，直到所有记录都排好序。
稳定性：不稳定
平均时间复杂度：$$O(nlogn)$$
/**
* @brief 快速排序
* 1、 从数列中挑出一个元素，称为"基准"（pivot）
* 2、 重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（相同的数可以到任何一边）。
* 在这个分区结束之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。
* 3、 递归地（recursively）把小于基准值元素的子数列和大于基准值元素的子数列排序。
* @param arr
*/
void quickSort(vector<int>& arr){
qsort(arr, 0, arr.size() - 1);
}
void qsort(vector<int>& arr, int low, int high) {
if (low >= high) return;
int pivot = partition(arr, low, high);
qsort(arr, low, pivot - 1);
qsort(arr, pivot + 1, high);
}
int partition(vector<int>& arr, int low, int high) {
int pivot = low++;
while (low < high) {
while (low < high && arr[high] >= arr[pivot]) --high;
while (low < high && arr[low] <= arr[pivot]) ++low;
if (low < high) swap(arr[low], arr[high]);
}
// 扫描完成，基准位置确定
swap(arr[pivot], arr[low]);
// 返回基准的位置
return low;
}堆排序
堆：
1、完全二叉树或者是近似完全二叉树。
2、大顶堆：父节点不小于子节点键值，小顶堆：父节点不大于子节点键值。左右孩子没有大小的顺序。
堆排序在选择排序的基础上提出的，步骤：
1、建立堆
2、删除堆顶元素，同时交换堆顶元素和最后一个元素，再重新调整堆结构，直至全部删除堆中元素。
稳定性：不稳定
平均时间复杂度：$$O(nlogn)$$
/**
* @brief 堆排序
* @note 堆排序在建立堆和调整堆的过程中会产生比较大的开销，在元素少的时候并不适用。但是，在元素比较多的情况下，还是不错的一个选择。
* 尤其是在解决诸如“前n大的数”一类问题时，几乎是首选算法。
*
*/
void heapSort(vector<int>& arr) {
if (arr.empty() || arr.size() == 1) return;
for (int i = 0; i < arr.size(); ++i) {
heapInsert(arr, i);
}
cout << "After heapInsert:";
displayArr(arr);
int last = arr.size();
swap(arr[0], arr[--last]);
while (last > 0) {
heapify(arr, 0, last);
swap(arr[0], arr[--last]);
}
}
void heapInsert(vector<int>& arr, int index) {
while (arr[index] > arr[(index - 1)/2]) {
swap(arr[index], arr[(index - 1)/2]);
index = (index - 1)/2;//递归检查父节点
}
}
void heapify(vector<int>& arr, int index, int heapSize) {
int left = index * 2 + 1;
while (left < heapSize) {
int largest = ( (left + 1 < heapSize) && (arr[left + 1] > arr[left])) ? left + 1 : left;
largest = arr[largest] > arr[index] ? largest : index;
if (largest == index) break;
swap(arr[largest], arr[index]);
index = largest;
left = index * 2 + 1;
}
}归并排序
采用分治思想，现将序列分为一个个子序列，对子序列进行排序合并，直至整个序列有序。
稳定性：稳定
平均时间复杂度：$$O(nlogn)$$
/**
* @brief 归并排序
* 递归法
* 1、 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
* 2、 设定两个指针，最初位置分别为两个已经排序序列的起始位置
* 3、 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
* 4、 重复步骤3直到某一指针到达序列尾
* 5、 将另一序列剩下的所有元素直接复制到合并序列尾
*
* 迭代法
* 1、 将序列每相邻两个数字进行归并操作，形成ceil(n/2)个序列，排序后每个序列包含两/一个元素
* 2、 若此时序列数不是1个则将上述序列再次归并，形成ceil(n/4)个序列，每个序列包含四/三个元素
* 3、 重复步骤2，直到所有元素排序完毕，即序列数为1
* @param arr
*/
void mergeSort(vector<int>& arr) {
vector<int> temp(arr.size());
internalMergeSort(arr, temp, 0, arr.size() - 1);
}
void internalMergeSort(vector<int>& arr, vector<int>& temp, int left, int right) {
if (left < right) {
int middle = (left + right) / 2;
internalMergeSort(arr, temp, left, middle);
internalMergeSort(arr, temp, middle+1, right);
mergeSortedArray(arr, temp, left, middle, right);
}
}
void mergeSortedArray(vector<int>& arr, vector<int>& temp, int left, int middle, int right) {
int i = left, j = middle + 1, k = 0;
while (i <= middle && j <= right) {
temp[k++] = arr[i] <= arr[j] ? arr[i++] : arr[j++];
}
while (i <= middle) {
temp[k++] = arr[i++];
}
while (j <= right) {
temp[k++] = arr[j++];
}
for (i = 0; i < k; ++i) {
arr[left + i] = temp[i];
}
}计数排序
思想：如果比元素x小的元素个数有n个，则元素x排序后位置为n+1。
步骤：
1）找出待排序的数组中最大的元素max_number；
2）统计数组中每个值为i的元素出现的次数，存入数组C的第i项；
3）对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）；
4）反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1。
稳定性：稳定
时间复杂度：$$O(n+k)$$k是待排序数的范围。
/** @brief 计数排序
@param array 数组指针
@param nLength_ 数组的最大长度
@param nMaxNumber_ 数组元素中的最大值
@note
计数排序的核心思想(来自算法导论）：
计数排序要求待排序的n个元素的大小在[0, k]之间，并且k与n在一个数量级上，即k=O(n).
对于每一个输入元素x, 确定小于等于x的个数为i。利用这一信息，就可以把元素x放到输出数组
的正确位置,即把元素x放到输出数组下标为i-1的位置。
重要说明：
1. 计数排序要求待排序的n个元素的大小在[0, k]之间，并且k与n在一个数量级上，即k=O(n).
此时使用计数排序可以把时间复杂度降到O(n)上。
2. 计数排序不是基于比较的排序算法，它基于计数策略。
3. 写计数排序算法时，应该把它写成稳定排序的。
4. 计数排序还是原址排序，它需要借助额外的内存空间。
任何比较排序算法的时间复杂度的上限为O(NlogN), 不存在比o(nlgN)更少的比较排序算法。
如果想要在时间复杂度上超过O(NlogN)的时间复杂度，肯定需要加入其它条件。计数排序就加入
了限制条件，从而使时间复杂度为O(N).
**/
void CountingSort(int array[], int nLength_, int nMaxNumber_)
{
// 参数的合法化检测
if (nullptr == array || nLength_ <= 1 || nMaxNumber_ <= 0)
return;
// 统计待排序数组中每一个元素的个数
// 注意：此处new出来的数组的大小为nMaxNumber_ + 1, 用于统计[0, nMaxNumber_]范围内的元素
int* ArrayCount = new int[nMaxNumber_ + 1]{0};
for (int i = 0; i < nLength_; ++i)
{
++ArrayCount[array[i]];
}
// 此处计算待排序数组中小于等于第i个元素的个数.
// 备注：如果要进行大到小的排序，就计算大于等于第i个元素的个数, 也就从后向前进行累加;
for (int i = 1; i < nMaxNumber_ + 1; ++i)
{
ArrayCount[i] += ArrayCount[i-1];
}
// 把待排序的数组放到输出数组中, 为了保持排序的稳定性，从后向前添加元素
int* ArrayResult = new int[nLength_];
for (int i = nLength_ - 1; i >=0; --i)
{
int _nIndex = ArrayCount[array[i]] - 1; // 元素array[i]在输出数组中的下标
ArrayResult[_nIndex] = array[i];
// 因为可能有重复的元素，所以要减1,为下一个重复的元素计算正确的下标;
--ArrayCount[array[i]];
}
// 交换数据并释放内存空间
memcpy(array, ArrayResult, sizeof(int) * nLength_);
delete [] ArrayCount;
ArrayCount = nullptr;
delete [] ArrayResult;
ArrayResult = nullptr;
}
// 测试代码
/*************** main.c *********************/
static void PrintArray(int array[], int nLength_);
int main(int argc, char* argv[])
{
int test[10] = {12, 12, 4, 0, 8, 5, 2, 3, 9, 8};
std::cout << "排序前：" << std::endl;
PrintArray(test, 10);
CountingSort(test, 10, 12);
std::cout << "排序后：" << std::endl;
PrintArray(test, 10);
return 0;
}
// 打印数组函数
static void PrintArray(int array[], int nLength_)
{
if (nullptr == array || nLength_ <= 0)
return;
for (int i = 0; i < nLength_; ++i)
{
std::cout << array[i] << " ";
}
std::cout << std::endl;
}桶排序
步骤：
1）设置一个定量的数组当作空桶子； 常见的排序算法及其复杂度：
2）寻访序列，并且把记录一个一个放到对应的桶子去；
3）对每个不是空的桶子进行排序。
4）从不是空的桶子里把项目再放回原来的序列中。
时间复杂度：$$O(n+C)$$ C为桶内排序时间。
/**
* @brief 桶排序
* 原理是将数组分到有限数量的桶子里，然后对每个桶子再分别排序
* （有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序），
* 最后将各个桶中的数据有序的合并起来。
* 1、 找出待排序数组中的最大值max、最小值min
* 2、 桶的数量为(max-min)/arr.length+1
* 3、 遍历数组 arr，计算每个元素 arr[i] 放的桶
* 4、 每个桶各自排序
* 5、 遍历桶数组，把排序好的元素放进输出数组
* @param arr
* @note 还有bug未解决
*/
void bucketSort(vector<int>& arr) {
if (arr.empty() || arr.size() == 1) return;
int min_num = INT32_MAX;
int max_num = INT32_MIN;
for (int i = 0; i < arr.size(); ++i) {
min_num = std::min(min_num, arr[i]);
max_num = std::max(max_num, arr[i]);
}
if (min_num == max_num) return;
int len = arr.size();
int bucketNum = (max_num - min_num) / len + 1;
vector<bool> hasNum(len + 1);
vector<int> max_(len + 1);
vector<int> min_(len + 1);
int bid = 0;
for (int i = 0; i < arr.size(); ++i) {
bid = bucket(arr[i], len, min_num, max_num);
min_[bid] = hasNum[bid] ? std::min(min_[bid], arr[i]) : arr[i];
max_[bid] = hasNum[bid] ? std::max(max_[bid], arr[i]) : arr[i];
hasNum[bid] = true;
}
// cout << "min_数组 : " << endl;
// displayArr(min_);
// cout << "max_数组 : " << endl;
// displayArr(max_);
int res = 0, lastMax= max_[0];
for (int i = 0; i < len; ++i) {
if (hasNum[i]) {
res = std::max(res, min_[i] - lastMax);
lastMax = max_[i];
cout << res << " ";
}
}
}
int bucket(long num, long len, long min, long max) {
return (int)((num - min) * len / (max - min));
}
