常见的排序算法有：
- 冒泡排序
- 快速排序
- 插入排序
- 归并排序
- 堆排序
1. 冒泡排序
冒泡排序是一种极其简单的排序算法，也是我所学的第一个排序算法。它重复地走访过要排序的元素，依次比较相邻两个元素，如果他们的顺序错误就把他们调换过来，直到没有元素再需要交换，排序完成。
优点:比较简单，空间复杂度较低，是稳定的
缺点:时间复杂度太高，效率不高
算法实现：
//冒泡排序
// 分类 -------------- 内部比较排序
// 数据结构 ---------- 数组
// 最差时间复杂度 ---- O(n^2)
// 最优时间复杂度 ---- 如果序列在一开始已经大部分排序过的话,会接近O(n)
// 平均时间复杂度 ---- O(n^2)
// 所需辅助空间 ------ O(1)
// 稳定性 ------------ 稳定
void HelloWorld::bubbleShort(int items[], int count) {
for (int i = 0; i < count - 1; i++)
{
for (int j = 0; j < count - 1 - i; j++)
{
if (items[j] > items[j + 1]) // 如果条件改成items[j] >= items[j+1],则变为不稳定的排序算法
{
int temp;
temp = items[j + 1];
items[j + 1] = items[j];
items[j] = temp;
}
}
}
}
1. 快速排序
快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下，排序n个元素要O(nlogn)次比较。在最坏状况下则需要O(n^2)次比较，但这种状况并不常见。事实上，快速排序通常明显比其他O(nlogn)算法更快，因为它的内部循环可以在大部分的架构上很有效率地被实现出来。
快速排序使用分治策略(Divide and Conquer)来把一个序列分为两个子序列。步骤为:
- 从序列中挑出一个元素，作为"基准"(pivot).
- 把所有比基准值小的元素放在基准前面，所有比基准值大的元素放在基准的后面（相同的数可以到任一边），这个称为分区(partition)操作。
- 对每个分区递归地进行步骤1~2，递归的结束条件是序列的大小是0或1，这时整体已经被排好序了。
优点：极快，数据移动少；
缺点：不稳定。
算法实现：
#include <iostream>
// 分类 ------------ 内部比较排序
// 数据结构 --------- 数组
// 最差时间复杂度 ---- 每次选取的基准都是最大（或最小）的元素，导致每次只划分出了一个分区，需要进行n-1次划分才能结束递归，时间复杂度为O(n^2)
// 最优时间复杂度 ---- 每次选取的基准都是中位数，这样每次都均匀的划分出两个分区，只需要logn次划分就能结束递归，时间复杂度为O(nlogn)
// 平均时间复杂度 ---- O(nlogn)
// 所需辅助空间 ------ 主要是递归造成的栈空间的使用(用来保存left和right等局部变量)，取决于递归树的深度，一般为O(logn)，最差为O(n)
// 稳定性 ---------- 不稳定
void Swap(int array[], int i, int j)
{
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
int Partition(int array[], int left, int right) // 划分函数
{
int pivot = array[right]; // 这里每次都选择最后一个元素作为基准
int tail = left - 1; // tail为小于基准的子数组最后一个元素的索引
for (int i = left; i < right; i++) // 遍历基准以外的其他元素
{
if (array[i] <= pivot) // 把小于等于基准的元素放到前一个子数组末尾
{
Swap(array, ++tail, i);
}
}
Swap(array, tail + 1, right); // 最后把基准放到前一个子数组的后边，剩下的子数组既是大于基准的子数组
// 该操作很有可能把后面元素的稳定性打乱，所以快速排序是不稳定的排序算法
return tail + 1; // 返回基准的索引
}
void QuickSort(int array[],int left,int right) {
if (left >= right) {
return;
}
int pivot_index = Partition(array, left, right); // 基准的索引
QuickSort(array, left, pivot_index - 1);
QuickSort(array, pivot_index + 1, right);
}
int main()
{
int array[] = {1,3,45,6,8,3,7,0,1,7,9};
int count = sizeof(array) / sizeof(array[0]);
QuickSort(array,0,count-1);
for (int i = 0; i < count; i++)
{
printf("%d \n", array[i]);
}
printf("++++++++");
return 0;
}
