1.排序算法的概念及其运用
1.1 排序的概念
** * 排序: **所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列 起来的操作。
*** 稳定性: **假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这 些记 录的相对次 序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列 中，r[i]仍在r[j]之前，则称这种排 序算法是稳定的；否则称为不稳定的。
*** 时间复杂度:**排序数据的总的操作次数。反映当n变化时，操作次数呈现什么规律。
*** 空间复杂度:**是指算法在计算机内执行时所需存储空间的度量，它也是数据规模n的函数。
*** 内部排序:**是指算法在计算机内执行时所需存储空间的度量，它也是数据规模n的函数。
*** 外部排序:**数据元素太多不能同时放在内存中，根据排序过程的要求不能在内外存之间移动数据的排序。
1.2 排序运用
像淘宝商品价格排序,各个学校的综合评分排名等，都运用了排序算法相关的知识.
1.3 常见的排序算法
2.常见排序算法的实现
2.1 插入排序
**基本思想**
直接插入排序是一种简单的插入排序法，其基本思想是：把待排序的记录按其关键码值的大小逐个插入到一 个已经排好序的有序序列中，直到所有
void InsertSort(int* a, int n)
{
//n:待排序数字的个数;n=sizeof(a)/sizeof(int);
assert(a);//函数断言
for (int i = 0; i < n - 1; ++i)
{
// 将x插入[0, end]有序区间
int end = i;
int x = a[end+1];
while (end >= 0)
{
if (a[end] > x)
{
a[end + 1] = a[end];
--end;
}
else
{
break;
}
}
a[end + 1] = x;
}
}
的记录插入完为止，得到一个新的有序 序 列实际中我们玩扑克牌时，就用了插入排序的思想.
2.1.1 直接插入排序 ** **
** *** 从第一个元素开始,该元素可以认为已经被排序;
** * **取出下一个元素，在已经排序的元素序列中从后向前扫描；
** * **如果该元素（已排序）大于新元素，将该元素移到下一位置；
** * **重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
** * **将新元素插入到该位置后；
** * **重复步骤2~5。
**动图演示: **
**代码实现:**
void InsertSort(int* a, int n)
{
//n:待排序数字的个数;n=sizeof(a)/sizeof(int);
assert(a);//函数断言
for (int i = 0; i < n - 1; ++i)
{
// 将x插入[0, end]有序区间
int end = i;
int x = a[end+1];
while (end >= 0)
{
if (a[end] > x)
{
a[end + 1] = a[end];
--end;
}
else
{
break;
}
}
a[end + 1] = x;
}
}
** 直接插入排序特性总结:**
1.元素集合越接近有序，直接插入排序算法的时间效率越高;
2. 时间复杂度：O(N^2) ;
3. 空间复杂度：O(1)，它是一种稳定的排序算法 ;
4. 稳定性：稳定;
2.1.2 希尔排序(缩小增量排序）
希尔排序法又称缩小增量法。希尔排序法的基本思想是：先选定一个整数，把待排序文件中所 有记录分成个 组，所有距离为的记录分在同一组内，并对每一组内的记录进行排序。然后 取, 重复上述分组和排序的工 作。当到达=1时，所有记录在统一组内排好序。
** 动图演示:**
** 代码实现:**
void ShellSort(int* a, int n)
{
//n:待排序数字的个数;n=sizeof(a)/sizeof(int);
// 多次预排序(gap > 1) +直接插入 (gap == 1)
int gap = n;
while (gap > 1)
{
//gap = gap / 2;
gap = gap / 3 + 1;
// 多组并排
for (int i = 0; i < n - gap; ++i)
{
int end = i;
int x = a[end + gap];
while (end >= 0)
{
if (a[end] > x)
{
a[end + gap] = a[end];
end -= gap;
}
else
{
break;
}
}
a[end + gap] = x;
}
}
}
** 希尔排序的特性总结: **
1. 希尔排序是对直接插入排序的优化。
2. 当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的 了，这样就 会很快。这样整体而言，可以达到优化的效果。我们实现后可以进行性能测试的对 比。
3. 希尔排序的时间复杂度不好计算，需要进行推导，推导出来平均时间复杂度： O(N^1.3— N^2）
4. 稳定性：不稳定
2.2 选择排序
** 基本思想:**
** **每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置， 直到 全部待排序的数据元素排完
2.2.1 直接选择排序
n个记录的直接选择排序可经过n-1趟直接选择排序得到有序结果。具体算法描述如下：
** * **初始状态：无序区为R[1..n]，有序区为空；
** *** 第i趟排序(i=1,2,3…n-1)开始时，当前有序区和无序区分别为R[1..i-1]和R(i..n）。该趟排序从当 前无序区中-选出关键字最小的记录 R[k]，将它与无序区的第1个记录R交换，使R[1..i]和 R[i+1..n) 分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区；
** *** n-1趟结束，数组有序化了。
**动图演示:**
** 代码实现: **
void swap(int* a, int* b)
{
int temp = *a;
*a = *b;
*b = temp;
}
void selectsort(int* a, int n)
{
assert(a);
for (int i = 0; i < n - 1; i++)
{
int min = i;
for (int j = i + 1; j < n; j++)
{
if (a[j] < a[min])
min = j;
}
swap(&a[min], &a[i]);
}
}
** 直接选择排序的特征总结:**
1. 直接选择排序思考非常好理解，但是效率不是很好。实际中很少使用
2. 时间复杂度：O(N^2)
3. 空间复杂度：O(1)
4. 稳定性：不稳定
2.2.2 堆排序
堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。它是通过堆来进行选择数据。需要注意的是排升序要建大堆，排降序建小堆。
** 动图演示:**
** 代码演示: **
void Adjustdown(int* a,int n,int parent)
{
int child = parent * 2 + 1;
while (child < n)
{
if (child + 1 < n && a[child + 1] > a[child])
{
child++;
}
if (a[child] > a[parent])
{
swap(&a[child], &a[parent]);
parent = child;
child = parent * 2 + 1;
}
else {
break;
}
}
}
void heapsort(int* a, int n)
{
assert(a);
for (int i = (n - 1 - 1) / 2; i >= 0; i--)
{
Adjustdown(a, n, i);
}
int end = n - 1;
while (end >= 0)
{
swap(&a[end], &a[0]);
Adjustdown(a, end, 0);
end--;
}
}
** 堆排序的特征总结:**
1. 堆排序使用堆来选数，效率就高了很多。
2. 时间复杂度：O(N*logN)
3. 空间复杂度：O(1)
4. 稳定性：不稳定
2.3 交换排序
** 基本思想**
所谓交换，就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置,交换排序的特点是：将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动。
2.3.1 冒泡排序
*** **比较相邻的元素。如果第一个比第二个大，就交换它们两个；
*** **对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；
*** **针对所有的元素重复以上的步骤，除了最后一个；
*** **重复步骤1~3，直到排序完成。
** 动图演示: ** 
** 代码实现:**
void swap(int* a, int* b)
{
int temp = *a;
*a = *b;
*b = temp;
}
void bubblesort(int* a, int n)
{
for (int i = 0; i < n - 1; i++)
{
for (int j = 0; j < n - 1 - i; j++)
{
if (a[j] > a[j + 1])
{
swap(&a[j], &a[j + 1]);
}
}
}
}
** 冒泡排序的特征总结:**
1. 冒泡排序是一种非常容易理解的排序
2. 时间复杂度：O(N^2)
3. 空间复杂度：O(1)
4. 稳定性：稳定
2.3.2 快速排序
快速排序使用分治法来把一个串（list）分为两个子串（sub-lists）。具体算法描述如下：
*** **从数列中挑出一个元素，称为 “基准”（pivot）；
*** **重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
*** **递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。
** 动图演示: **
** 代码实现:**
** 方式一**:hoare版本
int getmidindex(int* a, int left, int right)
{
int mid = (left + right) / 2;
if (a[left] < a[mid])
{
if (a[mid] < a[right])
return mid;
else if (a[left] > a[right])
return left;
else
return right;
}
else {
if (a[left] < a[right])
return left;
else if (a[mid] > a[right])
return mid;
else
return right;
}
}
int partion(int* a, int left, int right)
{
int mini = getmidindex(a, left, right);
swap(&a[mini], &a[left]);
int keyi = left;
while (left < right)
{
while (left<right && a[right]>=a[keyi])
right--;
while (left < right && a[left] <= a[keyi])
left++;
swap(&a[left], &a[right]);
}
swap(&a[left], &a[keyi]);
return left;
}
void quicksort(int* a, int left, int right)
{
if (left >= right)
{
return;
}
int keyi = partion(a, left, right);
quicksort(a, left, keyi - 1);
quicksort(a, keyi + 1, right);
}
** 方式二:挖坑法 **
int GetMidIndex(int* a, int left, int right)
{
//int mid = (left + right) / 2;
int mid = left + ((right - left) >> 1);
if (a[left] < a[mid])
{
if (a[mid] < a[right])
{
return mid;
}
else if (a[left] > a[right])
{
return left;
}
else
{
return right;
}
}
else // a[left] > a[mid]
{
if (a[mid] > a[right])
{
return mid;
}
else if (a[left] < a[right])
{
return left;
}
else
{
return right;
}
}
}
int Partion2(int* a, int left, int right)
{
// 三数取中 -- 面对有序最坏情况，变成选中位数做key，变成最好情况
int mini = GetMidIndex(a, left, right);
Swap(&a[mini], &a[left]);
int key = a[left];
int pivot = left;
while (left < right)
{
// 右边找小, 放到左边的坑里面
while (left < right && a[right] >= key)
{
--right;
}
a[pivot] = a[right];
pivot = right;
// 左边找大，放到右边的坑里面
while (left < right && a[left] <= key)
{
++left;
}
a[pivot] = a[left];
pivot = left;
}
a[pivot] = key;
return pivot;
}
** 方式三:前后指针法 **
int GetMidIndex(int* a, int left, int right)
{
//int mid = (left + right) / 2;
int mid = left + ((right - left) >> 1);
if (a[left] < a[mid])
{
if (a[mid] < a[right])
{
return mid;
}
else if (a[left] > a[right])
{
return left;
}
else
{
return right;
}
}
else // a[left] > a[mid]
{
if (a[mid] > a[right])
{
return mid;
}
else if (a[left] < a[right])
{
return left;
}
else
{
return right;
}
}
}
int Partion3(int* a, int left, int right)
{
// 三数取中 -- 面对有序最坏情况，变成选中位数做key，变成最好情况
int mini = GetMidIndex(a, left, right);
Swap(&a[mini], &a[left]);
int keyi = left;
int prev = left;
int cur = prev + 1;
while (cur <= right)
{
if (a[cur] < a[keyi] && ++prev != cur)
{
Swap(&a[cur], &a[prev]);
}
++cur;
}
Swap(&a[prev], &a[keyi]);
return prev;
}
** 快速排序的特征总结:**
1. 快速排序整体的综合性能和使用场景都是比较好的，所以才敢叫快速排序
2. 时间复杂度：O(N*logN)
3. 空间复杂度：O(logN)
4. 稳定性：不稳定
2.4 归并排序
归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。
***** 把长度为n的输入序列分成两个长度为n/2的子序列；
*** **对这两个子序列分别采用归并排序；
*** **将两个排序好的子序列合并成一个最终的排序序列。
**动图演示:**
** 代码实现:**
** 方式一:递归**
void _MergeSort(int* a, int left, int right, int* tmp)
{
if (left >= right)
{
return;
}
int mid = (left + right) / 2;
// [left, mid] [mid+1, right] 有序
_MergeSort(a, left, mid, tmp);
_MergeSort(a, mid + 1, right, tmp);
int begin1 = left, end1 = mid;
int begin2 = mid+1, end2 = right;
int i = left;
while (begin1 <= end1 && begin2 <= end2)
{
if (a[begin1] < a[begin2])
{
tmp[i++] = a[begin1++];
}
else
{
tmp[i++] = a[begin2++];
}
}
while (begin1 <= end1)
{
tmp[i++] = a[begin1++];
}
while (begin2 <= end2)
{
tmp[i++] = a[begin2++];
}
// tmp 数组拷贝回a
for (int j = left; j <= right; ++j)
{
a[j] = tmp[j];
}
}
void MergeSort(int* a, int n)
{
int* tmp = (int*)malloc(sizeof(int)*n);
if (tmp == NULL)
{
printf("malloc fail\n");
exit(-1);
}
_MergeSort(a, 0, n - 1, tmp);
free(tmp);
tmp = NULL;
}
** 方式二:非递归**
void MergeSortNonR(int* a, int n)
{
int* tmp = (int*)malloc(sizeof(int)*n);
if (tmp == NULL)
{
printf("malloc fail\n");
exit(-1);
}
int gap = 1;
while (gap < n)
{
for (int i = 0; i < n; i += 2 * gap)
{
// [i,i+gap-1] [i+gap,i+2*gap-1]
int begin1 = i, end1 = i + gap - 1;
int begin2 = i + gap, end2 = i + 2 * gap - 1;
// 核心思想：end1、begin2、end2都有可能越界
// end1越界 或者 begin2 越界都不需要归并
if (end1 >= n || begin2 >= n)
{
break;
}
// end2 越界，需要归并，修正end2
if (end2 >= n)
{
end2 = n- 1;
}
int index = i;
while (begin1 <= end1 && begin2 <= end2)
{
if (a[begin1] < a[begin2])
{
tmp[index++] = a[begin1++];
}
else
{
tmp[index++] = a[begin2++];
}
}
while (begin1 <= end1)
{
tmp[index++] = a[begin1++];
}
while (begin2 <= end2)
{
tmp[index++] = a[begin2++];
}
// 把归并小区间拷贝回原数组
for (int j = i; j <= end2; ++j)
{
a[j] = tmp[j];
}
}
gap *= 2;
}
free(tmp);
tmp = NULL;
}
** 归并排序的特征总结: **
1. 归并的缺点在于需要O(N)的空间复杂度，归并排序的思考更多的是解决在磁盘中的外排序问 题。
2. 时间复杂度：O(N*logN)
3. 空间复杂度：O(N)
4. 稳定性：稳定
3.排序算法复杂度及稳定性分析
以上是七大常见算法的相关知识点，有不足的地方或者对代码有更好的见解，欢迎评论区留言共同商讨，共同进步！！
版权归原作者 skeet follower 所有， 如有侵权，请联系我们删除。