目录
直接插入排序
直接插入排序的时间复杂度在最坏情况下是O(n2)，但在最佳情况下（即数据基本有序时）可以达到O(n)。
注意事项：每轮比较之前需将待插入数据保存，以免后续数据后移时将其覆盖
void InsertSort(int arr[], int length)
{
int i, j, key;
for (i = 1; i < length; i++)
{
key = arr[i]; // 待插入元素(首元素不动)
j = i - 1;
while (j >= 0 && arr[j] > key)
// 从后向前找插入位置
{
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}
头脑风暴：在寻找比key值小的数据时无需逐一比较，可以采用折半查找的方法快速确定插入位置，只不过该方法只能减少比较次数，无法减少元素的移动次数，所以实际上时间复杂度并未降低多少
希尔排序
对于d数列的取值非常灵活，理论上只要保证其为严格递减数列即可。但是不同的数列取值会导致算法的时间复杂度产生很大的区别，所以选取合适的d数列就是希尔排序要考虑的首要问题。
// 参数说明：
// arr: 待排序的数组
// length: 数组的长度
void ShellSort(int arr[], int length)
{
int i, j, temp;
int gap = 1; // 重新设置步长为1
while (gap < length / 3) // 初始步长设定为数组长度的1/3
{
gap = gap * 3 + 1; // 设置步长递增序列
}
while (gap > 0)
{
for (i = gap; i < length; i++)
{
temp = arr[i];
j = i - gap;
while (j >= 0 && arr[j] > temp)
{
arr[j + gap] = arr[j];
j -= gap;
}
arr[j + gap] = temp;
}
gap = (gap - 1) / 3; // 重新设置步长递减序列
}
}
⭐首个while循环是为了找到length长度序列下的最大对应步长，后续再进行步长的递减
选择排序
void SelectSort(int arr[], int length)
{
// i: 外层循环索引, j: 内层循环索引, minIndex: 最小值索引
for (int i = 0; i < length - 1; i++)
{
// 从当前位置开始找到最小值的索引
int minIndex = i;
for (int j = i + 1; j < length; j++)
{
if (arr[j] < arr[minIndex])
{
minIndex = j;
}
}
// 如果最小值的索引不等于当前位置索引,则交换两个位置的值
if (minIndex != i)
{
int temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
}
}
冒泡排序
// 对输入的数组 a 进行冒泡排序
// 参数：a - 待排序数组, n - 数组长度
void BubbleSort(int a[], int n) {
for(int i=0; i<n-1; i++) {
for(int j=0; j<n-i-1; j++) {
if(a[j] > a[j+1]) {
// 交换元素位置
int temp = a[j];
a[j] = a[j+1];
a[j+1] = temp;
}
}
}
}
算法优化：
1.当数列已经有序时,无需进行后续的比较冒泡
void BubbleSort(int a[], int n) {
for(int i=0; i<n-1; i++) {
bool swapped = false;
for(int j=0; j<n-i-1; j++) {
if(a[j] > a[j+1]) {
// 交换元素位置
int temp = a[j];
a[j] = a[j+1];
a[j+1] = temp;
swapped = true;
}
}
if (!swapped) {
// 如果本轮没有发生交换,则数组已经有序,提前结束排序
break;
}
}
}
2.利用bound与position的相互配合，以此判断是否某段数字已达顺序，避免重复排序而做了"无用功"，此升级版真乃环环相扣、步步推进，值得细细品味~
int main()
{
vector<int> arr;
int size, x;
cin >> size;
for (int i = 0; i < size; i++)
{
cin >> x;
arr.push_back(x);
}
int position = size - 1, bound;
while (position)
{
bound = position;
// bound 指每轮的比较次数,其与position有关
// position 指上一轮排序之后从哪个位置开始的数已达到顺序
// position 位置及其之前的数是不一定为顺序
position = 0;
// 令position为 0是为了判断是否进行了交换数据的操作,如果没有则说明全部顺序,跳出循环
for (int i = 0; i < bound; i++)
{
if (arr[i] > arr[i + 1])
{
int tmp = arr[i + 1];
arr[i + 1] = arr[i];
arr[i] = tmp;
position = i;
// position 赋值为i是为了确定达到顺序的数的位置,并由此确定下一轮循环比较次数
}
}
}
return 0;
}
思维拓展：
- 冒泡排序中元素交换的次数即为序列中逆序数对的个数：[0， n(n-1)/2]
- 若间隔大于1的数对为逆序对，则由该数对及其中间的数所构成的子序列中必有相邻的逆序数对
- 所以，当相邻的逆序数对全部被消除后，数列必有序
快速排序
核心思想：通过交换不相邻的元素可以快速减少逆序数，当逆序数对减少到0时数列有序。
void QuickSort(int left, int right)
{
int i = left, j = right, temp;
// 若left >= right,则说明数组中只有一个元素或为空,无需排序
if (left >= right)
return;
// 选择第left个元素作为基准
temp = arr[left];
while (i != j)
{
// 从右边开始找比基准小的元素
while (arr[j] >= temp && i < j)
j--;
// 从左边开始找比基准大的元素
while (arr[i] <= temp && i < j)
i++;
// 交换i和j指向的元素
if (i < j)
{
int t = arr[i];
arr[i] = arr[j];
arr[j] = t;
}
}
// 经过上述循环后,i=j,将基准元素归位
arr[left] = arr[i];
arr[i] = temp;
// 递归左右两边
quickSort(left, i - 1);
quickSort(i + 1, right);
return;
}
思维拓展：快速排序性能分析
最佳情况：当基准数刚好取到序列的中位数时（即划分后基准数将序列等分）Ο(nlogn)
最坏情况：当基准数每次都取到序列的最大/小值时（一轮划分只可归位一个元素）Ο(n^2)
平均情况：
Ⅰ.每个元素作为基准的可能性都为1/n
Ⅱ.所有的基准数划分出的子序列的长度之比平均为1:3
Ⅲ.由计算得知有80%的概率使得划分的序列长度之比优于1:9。这使得快速排序的时间期望较优
Ⅳ.实际上，只要不是每一次基准数都取到序列的最大值或最小值，则无论比例 Y 有多小，都可以从理论上证明时间复杂度为Ο(nlogn)。只不过 Y 越大， nlogn前面的系数越大
快速排序的核心思想就是寻找基准值并由此将整体序列分而治之
思维点睛：快速排序优化
1.三数取中法
简化版的三数取中法可以在arr [left] 、arr [right]、arr [(left +right)/2] 之间寻找中位数再以其为基准即可
//寻找三个数的中位数
int FindMedian(int a, int b, int c)
{
if ((a - b) * (c - a) >= 0)
{
return a;
}
else if ((b - a) * (c - b) >= 0)
{
return b;
}
else
{
return c;
}
}
//找到基准数即其下标
// 三数取中法选择基准
int tmp, index;
int mid = (left + right) / 2;
tmp = FindMedian(arr[left], arr[mid], arr[right]);
if (tmp == arr[left])
{
index = left;
}
else if (tmp == arr[right])
{
index = right;
}
else
{
index = mid;
}
//将基准数归位
// 经过上述循环后,i=j,将基准元素归位
arr[index] = arr[i];
arr[i] = tmp;
2.快速排序其余实现及优化方法见以下网站：
归并排序
二路归并算法
核心思想：将两个有序序列合并为新的有序序列
// 注意输入sx,sy,ex,ey的时候保证子序列为升序排列
int *TwoWayMerge(int arr[], int sx, int sy, int ex, int ey)
{
// 新序列res长度为ex+ey-sx-sy
int *res = new int[ex + ey - sx - sy + 2];
int i = sx, j = sy, k = 0;
// 只要i,j没同时越界,就进入循环
while (i <= ex || j <= ey)
{
// 当arr[i]<=arr[j]且i未越界时,将arr[i]放入res,i++,k++
// 当j越界时,将arr[i]剩余元素放入res,i++,k++
if (((arr[i] <= arr[j]) && i <= ex) || (j > ey))
{
res[k++] = arr[i++];
}
else
{
res[k++] = arr[j++];
}
}
return res;
}