? ? 我们日常生活中，很多地方都需要使用排序方法，比如你逛淘宝，天猫👇👇👇👇👇👇
? ? 你想要买一些便宜的或者贵的，或者性价比比较高的，都可以按照你的需求给你排列出来，这么多种物品， 总有一款是适合你的~~~这里就使用到了排序算法👇 👇👇👇👇👇👇👇👇👇👇👇👇👇👇。介绍数据结构中几种比较常用的排序方法~~~
目录
1.插入排序
? ? 插入排序思想比较简单，在我个人看来插入排序和冒泡排序有一点相似，但是他们说这两个排序思想根本不是一回事~~~~插入排序的思想和日常生活中大家玩的扑克牌的思想就很相似，你揭的第一张牌默认为有序，再来的扑克你分一下是比第一张牌大or小你就放在一个合适的位置~~~~~~
我们通过动图来了解插入排序的思想👇👇👇👇👇
通过上面这样子，乱序数组就会被安排在有序的位置里了~~~~再来看一下代码实现👇?👇👇👇👇👇
void Insert(int* arr, int n)
{
//总体需要拍的数据，我们假设是最坏的情况，里面的每一个
//数据都是需要被调整的~
int i = 0;
for (i = 0; i < n-1; i++)
{
//我们从第一个数据下标位置开始调整~
int end = i;
//先使用临时变量记录第一个数据位置下一个位置的
//值，
int x = arr[end +1];
while (end >= 0)
{
//开始判断排序
if (x < arr[end])
{
//如果后一个位置值小于这个位置值那么就使用第一个
//位置值来将下一个位置的值覆盖，end--判断是否后面的值
//还是小于x的
arr[end + 1] = arr[end];
end --;
}
else
break;
}
arr[end + 1] = x;
}
}?
?这样依次递归下去
? ? Notice：
? ? 我们会注意到无论哪种算法，它们排序的天花板就是0（n），因为基本条件就是需要把整个数组遍历一下，上面的插入排序我们可以发现，它的最佳情况就是o(n),最糟糕的情况是o(n^2)的了，假设数组降序排为升序~~~~~~~
🎄希尔排序
?introduce：
? ? 希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。但希尔排序是非稳定排序算法。
希尔排序是基于插入排序的以下两点性质而提出改进方法的：
- 插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率；
- 但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位；
? ? 希尔排序的基本思想是：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录"基本有序"时，再对全体记录进行依次直接插入排序。我们来看一下动图吧👇
👇👇👇👇👇👇👇
? ?希尔排序是根据插入排序进行优化的，我们前面已将提到，如果插入排序情况比较好的情况下，就是有的数字不需要处理，那么复杂度可能会降到o(n),那么希尔的思想就是，我可不可先将它大致整理一下再进行排序呢？
?我们先将这几个数组，每隔3个取一个数据将他们进行预排序~~那么它们使用插入排序的方式排完之后就是这个样子👇👇👇👇👇👇👇👇
可以看出它比第一次有序了，最小的和最大的分别都到了相应的位置~~~~~再次进行预排序~~~
那么这次的预排序我们就不在使用已经排好的数据了👇?👇?👇?👇?👇?👇?👇?
这次我们选择了相比第一次后一个位置数字进行预排序，那么这几个数字排完是这个样子👇👇👇👇👇👇👇👇
又比之前好了一些，我们再来一次👇?👇👇👇👇👇👇
这次排完已经很接近有序了，但是还是在需要进行依次插排，数据才会被排序好~~再进行一次插排的话加上我们之前的三次预排序我们一共处理了四次，好像原来越接近普通插入排序了~~~~~~我们来看一下代码实现👇?👇?👇?👇?👇?👇?👇?👇?👇?
int gap=3;
for (i = 0; i < n - gap; i+=gap)
{
int end = i;
int x = arr[end + gap];
while (end >= 0)
{
if (x < arr[end])
{
arr[end + gap] = arr[end];
end -= gap;
}
else
break;
}
arr[end + gap] = x;
}?这是第一次预排序，后面两次预排序我们emit..........
整体代码实现👇👇👇👇👇👇👇👇👇👇👇👇👇👇
void Shellsort(int* arr, int n)
{
int gap = n;
int end = 0;
int i = 0;
while (gap > 1)
{
gap /= 3;
for (i = 0; i < n - gap; i++)
{
int end = i;
int x = arr[end + gap];
while (end >= 0)
{
if (x < arr[end])
{
arr[end + gap] = arr[end];
end -= gap;
}
else
break;
}
arr[end + gap] = x;
}
}?我们第一次使gap=gap/2=5，其实即是将数字两两分开进行预排👇👇👇👇👇👇👇👇👇
👇
? ? ?排完之后是这个样子~~这次是整体变化比较大。我们再使gap=gap/4=2;就可以得到更接近插入排序的~~这个希尔排序大致思想就是这样，比较不容易理解~~
? ???Analyze：
? ? 时间复杂度最坏情况下还是o(n^2);😅，最好情况下则为o(n)。技术牛们说希尔排序平均下来复杂度在o(n^1.3)不知道从哪里的得到的结论~~
🎋插排希尔性能对比
? ? 我们创建一组数据进行插入和希尔的性能比较👇👇👇👇👇👇👇
void test()
{
srand(time(0));
const int N = 100000;
int* a1 = new int[N];
int* a2 = new int[N];
int* a3 = new int[N];
int* a4 = new int[N];
int* a5 = new int[N];
int* a6 = new int[N];
//int* a7 = new int[N];
for (int i = 0; i < N; i++)
{
a1[i] = rand();
a2[i] = a1[i];
a3[i] = a1[i];
a4[i] = a1[i];
a5[i] = a1[i];
a6[i] = a1[i];
}
//记录时间点
int begin = clock();
Insert(a1, N);
int end = clock();
cout << (end - begin) << endl;
int begin1 = clock();
Shellsort(a2,N);
int end1 = clock();
cout << (end1 - begin1) << endl;
}
我们得到的结果是我们排列100000个数据插排耗费3.67s。而希尔排序只耗费0.015s.我们只是得到了结论，希尔排序是一种比较稳定的排序方法，而且希尔这人也是真的厉害。这都能想到~~
🎄堆排序
? ? 堆排序是指利用堆积树，这种数据结构所设计的一种排序算法，属于选择排序的一种。它是通过堆来进行数据选择，需要注意的是排升序需要建大堆，排降序需要建小堆~~👇👇👇👇👇👇👇👇👇我们演示一个排序升序的堆排~~~
void Heapsort(int* a, int n)
{
for (int i = (n-2)/2; i >= 0; i--)
{
AdjustDown(a, n, i);
}
for (int i = 0; i < n; i++)
{
cout << a[i] << " ";
}
cout << endl;因为我们需要建一个大堆，之前的插入已经不行了，比如这样的👇👇👇👇
?所以我们就需要从下往上面调~~这样就可以把它搞成一个大堆~~大堆建立完之后，就开始我们的堆排👇👇👇👇
void AdjustDown(int* a, int n, int parent)
{
int child = parent * 2 + 1;
while (child < n)
{
//选出两个孩子中较小的那一个
if (child + 1 < n && a[child] < a[child + 1])
{
child++;
}
//如果符合条件就交换
if (a[parent] < a[child])
{
Swap(&a[parent], &a[child]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
void Heapsort(int* a, int n)
{
这里需要从下向上把堆建成大根堆
for (int i = (n-2)/2; i >= 0; i--)
{
AdjustDown(a, n, i);
}
int end = n - 1;
while (end > 0)
{
//与堆顶元素进行互换~~
Swap(&a[0], &a[end]);
//然后将堆顶的元素往下调，注意这里调不到原来的位置，相当于删除~~
AdjustDown(a, end, 0);
//依次向上遍历~·
end--;
}
}?🎋堆排性能对比
?可以看出堆排和希尔排序还是在一个级别的~
- 堆排时间复杂度为o(N*logN),建堆时间复杂度为o(n);
- 空间复杂度为o(1);
- 堆排稳定性不好i~~
🎄冒泡排序
? ? 冒泡排序是非常稳定的排序方式，而且比较容易理解👇👇👇👇👇👇
void Bubblesort(int* a, int n)
{
int i = 0;
for (i = 0; i < n - 1; i++)
{
int flag = 0;
int j = 0;
for (j = 0; j < n - i - 1; j++)
{
if (a[j] < a[j + 1])
{
flag = 1;
Swap(&a[j], &a[j + 1]);
}
}
if (flag == 0)
break;
}
}??🎋冒泡性能对比度
- ?冒泡排序很容易理解，也很稳定，属实有些慢了基本上都是o(N^2);
- 最坏情况为o(N^2),最好的为o(N）~~~
🎄选择排序
? ? 选择排序思想较为简单，就是打擂台的方法，选出最大或者最小的数字，然后排列称为升序或者降序只不过这次的选择排序，一次选出了最大数和最小数，相当于是量变~~👇👇👇👇👇👇👇、
? ? 标记起始位置和最后的位置，让最大的和end交换，最小的和begin交换。这里面的一个小bug是如果最大值在第一位，那么最大值就会先被换走。就是上面这种情况，那么我们就需要稍微做一下处理~~~~👇👇👇👇👇
int begin = 0, end = n-1;
while(begin<end)
{
int mini = begin, maxi = begin;
for (int i = begin; i <= end; i++)
{
if (a[i] > a[maxi])
{
maxi = i;
}
if (a[i] < a[mini])
{
mini = i;
}
}
Swap(&a[maxi], &a[end]);
//判断一下是否是上面说的那种情况~~
if (maxi == begin)
{
maxi = mini;
}
Swap(&a[mini], &a[begin]);
begin++, end--;
}🎋选择排序性能对比
?论效率来说还是堆排和希尔是比较快的~~
🎄快速排序
?🎋快排递归版本
我们先演示一趟单趟的~~👇👇👇👇👇👇👇
?Noitice ：如果keyi给的是左边的值，就需要先从右边开始查找~~~~
? ? ? ? ? ? ? ? ? ? ? 如果keyi给的是右边的值，就需要从左边的值开始进行查找~
? ? ? ? ? ? ? ? ? ? ? ?这里还需要注意一些小bug，就是越界的情况~~~~
int Partion(int* a, int left, int right)
{
int keyi = left;
while (left < right)
{
//从右边开始,找比keyi小的数，
while (left<right&&a[right] >= a[keyi])
{
right--;
}
//从左边开始,找比keyi大的数，
while (left<right&&a[left] <= a[keyi])
{
left++;
}
Swap(&a[left], &a[right]);
}
Swap(&a[keyi], &a[left]);
return left;
}? ? ?完成这个快速排序是需要我们对它进行分区间的，也就是分治问题， 将它分为以keyi隔开的区间，逐个进行排序，这里就使用到了递归来进行~~👇👇👇👇👇👇👇👇👇👇
?我们来看一下代码实现~~其实也还好👇👇👇👇👇👇
int Partion(int* a, int left, int right)
{
int keyi = left;
while (left < right)
{
//从右边开始,找比keyi小的数，
while (left<right&&a[right] >= a[keyi])
{
right--;
}
//从左边开始,找比keyi大的数，
while (left<right&&a[left] <= a[keyi])
{
left++;
}
Swap(&a[left], &a[right]);
}
Swap(&a[keyi], &a[left]);
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);
}?Summary：递归版本省事比较简单，但是有时候递归太多就容易栈溢出，
🎋挖坑法
? ? ? 挖坑法就是在原来的基础上进行了改进~先设置一个坑位，先让右边的走，找到小的就停止，然后把值给到坑位。让right变成新的坑位，再让左边走，和右边类似，注意最后跳出循环，需要让最后的坑位等于key值然后返回坑位~
int Partionpit(int* a, int left, int right)
{
int key = a[left];
//设置的坑位
int pit = left;
while (left < right)
{
while (left < right && a[right] >= key)
{
right--;
}
a[pit] = a[right];
pit = right;
while (left < right && a[left] <= key)
{
left++;
}
a[pit] = a[left];
pit = left;
}
a[pit] = key;
return pit;
}🎋双指针法
? ??
int Partoinpointer(int* a, int left, int right)
{
//两个指针
int key = left;
int slow = left, fast = left +1;
while (fast < right)
{
if (fast<right&&a[fast] < a[key])
{
Swap(&a[++slow], &a[fast]);
}
fast++;
}
Swap(&a[key], &a[slow]);
return slow;
}
void Quicksort(int* a, int left, int right)
{
if (left >= right)
{
return;
}
int keyi = Partoinpointer(a, left, right);
Quicksort(a, left, keyi - 1);
Quicksort(a, keyi + 1, right);
}?
选key的两种情况~~?
?🎋 快排非递归版本
? ? 快排的递归版本我们可以想到， 但是递归的缺点就是递归的太深，容易栈溢出，如果是一组比较有序的数组，递归版本就会进行的很深~~快排非递归版本是使用到栈的思想来进行👇👇👇👇👇
void QuickSortNonR(int* a, int left, int right)
{
stack<int> st;
st.push(left);
st.push(right);
while (!st.empty())
{
//开始取栈内元素
int end = st.top();
st.pop();
int begin = st.top();
st.pop();
int keyi = Partionpit(a, begin, end);
//处理过之后区间被分为[begin,key-1],keyi,[keyi+1,end];
//被分为两个区间的选择先入右边，这样就会先处理左边~
//判断是区间是否还有，有的话就继续入，或者相等就入了~~
if (keyi + 1 < end)
{
st.push(keyi + 1);
st.push(end);
}
if (begin < keyi - 1)
{
st.push(begin);
st.push(keyi-1);
}
}
}?
🎋快排性能对比
? ??
?在相对效率都较高的情况，快排还是非常稳定的~~
🎄归并排序
? ? 归并排序（Merge sort）是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。
作为一种典型的分而治之思想的算法应用，归并排序的实现由两种方法：
- 自上而下的递归（所有递归的方法都可以用迭代重写）；
? 算法思想：
-
申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列；
-
设定两个指针，最初位置分别为两个已经排序序列的起始位置；
-
比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置；
-
重复步骤 3 直到某一指针达到序列尾；
-
将另一序列剩下的所有元素直接复制到合并序列尾。
动图演示：
? ? ?
? ? ?归并排序就是将区间细分，分治来达成目的~~
👇👇👇👇👇👇👇👇👇👇
? ??
void _Mergesort(int*a,int left,int right,int*tmp)
{
//递归到最后一个子区间就返回，在返回过程中完成归并~~
if (left >= right)
{
return;
}
int mid = (left + right) / 2;
_Mergesort(a, left, mid, tmp);
_Mergesort(a, mid + 1, right, tmp);
int begin1 = left, end1 = mid, 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排序好的再拷贝回原来的空间~所以空间复杂度较高~
int j = left;
for (j = left; j <= right; j++)
{
a[j] = tmp[j];
}
}
void Mergesort(int *a,int n)
{
int* tmp = new int[n];
_Mergesort(a, 0, n - 1, tmp);
delete[]tmp;
tmp = nullptr;
}??性能对比
? ??
?
? ? ?最稳定的还是希尔和归并~~·
👆👆👆👆👆👆👆👆👆👆👆👆👆👆👆👆👆👆👆👆👆👆👆👆👆👆👆👆👆👆👆👆👆👆👆👆
