详解排序几大算法
一、插入排序根本头脑：
[*]直接插入排序是一种简单的插入排序算法，其根本头脑是：把待排序的记载按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记载插入完为止，得到一个新的有序序列。
步骤：
当插入第n个元素的时间前面的arr到arr都已经排序好了，此时我们将arr与前面的相比力，假设我们必要一个升序的数组，那当arr小于所比力的这个数的时间，就跟其交换位置，原来位置上的元素顺序后移。
动图演示：
https://i-blog.csdnimg.cn/direct/7870fddc2dce425d9fa40cc76eee6c0b.gif#pic_center
代码实现：
void InsertSort(int* a, int n)
{
for (int i = 0; i < n-1; i++)
{
//记录最后一个元素的下标
int end = i ;
//待排序的数据
int tmp = a;
while (end >= 0)
{
//比插入的数大就往后
if (a > tmp)
{
a = a;
end--;
}
//比插入的数小就跳出循环
else
{
break;
}
}
a = tmp;
}
}
直接插入排序的特性：
[*]元素聚集越接近有序，直接插入排序算法的时间服从就越高
[*]时间复杂度：O（N^2）
[*]空间复杂度：O(1)
二、希尔排序
根本头脑：
[*]先选定一个整数(通常是gap = n/3+1)，把待排序文件所有记载成各组，所有的间隔相等的记载在同一组内，并对每一组内的记载进行排序，然后gap = gap/3+1得到下一个整数，再将数组分成各组，进行插入排序，当gap = 1时，将相当于直接插入排序。
[*]所有我们会发现希尔排序是直接插入算法的根本上进行改进而来，但是它的服从要高于直接插入排序。
https://i-blog.csdnimg.cn/direct/7f9af09dbf3440d1ab757f2e9b4436ab.png
动图演示：
https://i-blog.csdnimg.cn/direct/b59ce7c100e340adb55f0337cd948c7e.gif#pic_center
希尔排序的特性：
[*]希尔排序是对直接排序的优化
[*]当gap > 1时都时预排序，目标是让数组更接近于有序。当gap == 1时，数组已经接近有序的了。
代码实现：
void ShellSort(int* a, int n)
{
int gap = n;
while (gap>1)
{
gap = gap / 3 + 1;
//单趟排序
for (int i = 0; i < n - gap; i++)
{
int end = i;
int tmp = a;
while (end >= 0)
{
if (a > tmp)
{
a = a;
end -= gap;
}
else
{
break;
}
}
a = tmp;
}
}
}
希尔排序的时间复杂度：O(n^3/2)
希尔排序的空间复杂度：O(1)
三、选择排序
根本头脑：
每次从待排序的数据元素中选最小（大概最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。
直接选择排序步骤：
[*]在元素聚集 array–array 中选择关键码最⼤(小)的数据元素
[*]若它不是这组元素中的最后⼀个(第⼀个)元素，则将它与这组元素中的最后⼀个（第⼀个）元素交换
[*]在剩余的 array–array（array–array） 聚集中，重复上述步骤，直到聚集剩余 1 个元素
动图演示：
https://i-blog.csdnimg.cn/direct/ff5cda0811624bb3a9c988b99aeda97c.gif#pic_center
代码实现：
void SelectSort(int* a, int n)
{
int begin = 0, end = n - 1;
while (begin < end)
{
int mini = begin, maxi = begin;
for (int i = begin; i <= end; i++)
{
if (a > a)
{
maxi = i;
}
if (a < a)
{
mini = i;
}
}
if (begin == maxi)
{
maxi = mini;
}
swap(&a, &a);
swap(&a, &a);
++begin;
--end;
}
}
直接选择排序的时间复杂度：O(N^2)
直接选择排序的空间复杂度：O(1)
四、堆排序
堆排序是指利用堆积树这种数据布局所筹划的一种排序算法，它是选择排序的一种。
我们必要注意的是排升序要建大堆，排降序建小堆。
点这里在二叉树内里实现了堆排序
五、冒泡排序
动图演示：
https://i-blog.csdnimg.cn/direct/4f9b1ca35b84479abd9e873078e01e51.gif#pic_center
代码实现：
//冒泡排序
void BubbleSort(int* arr, int n)
{
int end = n;
while (end)
{
int flag = 0;
for (int i = 1; i < end; ++i)
{
if (arr > arr)
{
int tmp = arr;
arr = arr;
arr = tmp;
flag = 1;
}
}
if (flag == 0)
{
break;
}
--end;
}
}
冒泡排序的时间复杂度：O(N^2)
冒泡排序的空间复杂度：O(1)
六、快速排序
根本头脑：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序聚集分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。
hoare版本
算法头脑：
1.创建左右指针，确定基准值
2.从右向左找出比基准值小的数据，从左往右找出比基准值大的数据，左右指针数据交换，进入下一次循环
步骤：
我们选定一个key（一般是最右边的数，大概最左边的数）接着我们必要定义一个begin和一个end，begin是从左往右走，end是右往左走。在它们走的过程中，当begin遇到比key大的数据的时间停下来，end继承走，指导遇到一个小于key的数时，两者交换数据，最后直到它们相遇，相遇点的数据和key的数据交换。
动图演示：
https://i-blog.csdnimg.cn/direct/62b25fcbcb214615afe7a6864252aaab.gif#pic_center
void QuickSort(int* a, int begin, int end)
{
if (begin >= end)
return;
int left = begin;
int right = end;
//选左边为key
int keyi = begin;
while (begin < end)
{
while (a >= a && begin < end)
{
--end;
}
//左边选大
while (a <= a && begin < end)
{
++begin;
}
//小的换到右边，大的换到左边
swap(&a, &a);
}
swap(&a, &a);
keyi = end;
QuickSort(a, left, keyi - 1);
QuickSort(a,keyi + 1,right);
}
挖坑法
根本思路：
创建左右指针，首先从右往左找出比基准值小的数据，后将其放在左边坑中，当前的位置就变为新的坑，然后在从左往右找出比基准值大的数据，找到后将其放进右边坑中，当前位置变为新的坑，当竣事循环的时间将最开始储存的分界值放进当前的坑中，返回当前坑的下标。
步骤：
选出一个数据（可以是最左也可以是最右，一般情况下）存放在key变量中，在这个数据位置形成一个坑，紧接着我们定义一个Left和一个Right，Left从左往右走，Right从右往左走。
必要注意的是如果最左边挖坑，则必要Right先走；反之，则Left先走。
动图演示：
https://i-blog.csdnimg.cn/direct/bf9175e1c52e463ba5cbd8f76f69d019.gif#pic_center
代码实现：
void QuickSort1(int* a, int begin, int end)
{
if (begin >= end)
{
return;
}
int left = begin,right = end;
int key = a;
while (begin < end)
{
//找小
while (a >= key && begin < end)
{
--end;
}
//小的放到左边的坑里
a = a;
//找大
while (a <= key && begin < end)
{
++begin;
}
//大的放到右边的坑里
a = a;
}
a = key;
int keyi = begin;
QuickSort1(a, left, keyi - 1);
QuickSort1(a, keyi + 1, right);
}
lomuto前后指针
根本思路：
创建前后指针从左往右找比基准值小的进行交换，使得小的都排在基准值的左边。
步骤：
选出一个key，起始时prev指针指向序列开头，cur指针指向prev+1的位置。若cur指向的数据小于key，则prev先向后移动一位，然后将prev和cur指针指向的数据交换，cur++；若cur指向的数据大于key，则cur指向直接++。如此进行下去，直到cur到达end位置，此时将key和++prev指针指向的数据交换即可。
https://i-blog.csdnimg.cn/direct/9fef5b8af460452fa31515c7ac0baf19.gif#pic_center
代码实现：
void QuickSort2(int* arr, int begin, int end)
{
if (begin >= end)
{
return;
}
int cur = begin, prev = begin - 1;
int keyi = end;
while (cur != keyi)
{
if (arr < arr && ++prev != cur)
{
swap(&arr, &arr);
}
++cur;
}
swap(&arr[++prev],&arr);
keyi = prev;
QuickSort2(arr, begin, keyi - 1);
QuickSort2(arr, keyi + 1, end);
}
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]