数据结构-排序

目录

一、冒泡排序

二、选择排序

三、插入排序

四、希尔排序

五、堆排

六、快速排序

1、hoare：

2、挖坑法：

3、前后指针法：

 4、快排非递归

七、归并排序

1、递归写法：

2、非递归写法：

八、计数排序

九、排序的时间复杂度和空间复杂度以及稳定性

1、稳定性：

---

一、冒泡排序

###思想：

有几个数据就进行几次排序，每一次比较两个挨着的数据大小，把大的往后放；每一次排序走完，下一次就不需要再排这个数据，也就是说已经放在后面的数据不需要排，并且每次排序比较的次数是一个等差数列;

###图像：

###代码：

//冒泡排序
void BubbleSort(int* arr, int size)
{for (int i = 0; i < size; i++){int flag = 0;for (int j = 0; j < size - i - 1; j++){if (arr[j] > arr[j + 1]){swap(arr[j], arr[j + 1]);flag = 1;}}if (flag == 0){break;}}
}

###时间复杂度：O（N^2）；flag优化，当进行一趟没有交换时，说明已经有序，无需再排，此时直接退出优化效率

二、选择排序

###思想：遍历数据，选出最大最小的数分别放在首位；

###代码：

//选择排序
void SelectSort(int* arr, int left,int right)
{int begin = 0, end = right - 1;while (begin < end){int maxi = begin;int mini = begin;for (int i = begin+1; i <= end; i++){if (arr[maxi] < arr[i]){maxi = i;}if (arr[mini] > arr[i]){mini = i;}}swap(arr[mini], arr[begin]);if (maxi == begin){maxi = mini;}swap(arr[maxi], arr[end]);begin++;end--;}
}

###时间复杂度为O（N^2），是所有排序中最差的，冒泡排序至少还有优化。

三、插入排序

###思想：

每次默认前面一段有序，从紧挨着这一段有序数据的下一个数据开始往前比较，若是比前面的小，就让前面的移到后面一个的位置，直至找到比这个数据小的数就不再移动，将这个数据插入到这里

###图像：

###代码：

//插入排序
void InsertSort(int* arr, int size)
{for (int i = 0; i < size - 1; i++){int end = i;int tmp = arr[end + 1];while (end >= 0){if (arr[end] > tmp){arr[end + 1] = arr[end];}else{break;}end--;}arr[end + 1] = tmp;}
}

跳出循环的条件有两个：一是找到比tmp小的数了，此时break，让tmp插到end+1的位置，因为end的位置的数据恰好是比tmp小的；二是end小于0了，此时说明tmp前面没有比它小的值，0位置的数据也被移到后面一位的位置上了，那么就要把tmp放在0的位置，也就是end+1。那么这两种情况这种写法都兼容；

若是在循环里面插入tmp，那么当end小于零时，还要跳出循环之后再判断end是不是大于零再插入；

###时间复杂度：O（N^2）；但是比冒泡和选择都好一点。插入排序每次的end都在增加，也就是每次循环的次数在减少，内层循环是一个等差数列；虽然冒泡也是，但是插入排序一旦找到比tmp小的就会跳出，此轮循环结束；冒泡排序虽然有优化，但是在大量数据面前做到提前有序的几率很小，至少小于插入排序每轮提前找到比tmp小的数据的几率（因为只有当数据是逆序时，插入排序才会每趟循环都走完，而此种情况出现的几率极小）

总之就是：插入排序和冒泡排序虽然都是相同量级的时间复杂度，但是极大几率插入排序优于冒泡排序。

四、希尔排序

###思路：

希尔排序可以说是插入排序的优化；从第一个数据开始，和它每间隔gap个位置的数据进行插入排序；这样的排序被称为一次预排序，gap是几那么就要进行几次预排序，因为gap之间的数据并有被分在同一次预排序里面，这就说明要分多次预排序，这个多次就是gap次；

进行完一次预排序，大的数据会渐渐跑到后面，小的数据渐渐跑到前面，那么数据就是更接近有序的；gap是要慢慢减小的，最后为1，进行插入排序，因为进行了预排序，那么最后进行插入排序时就会很快；这样就达到了优化的效果；

###代码：

//希尔排序
void ShellSort(int* arr, int size)
{int gap = size;while (gap > 1){gap = gap / 3 + 1;//保证最后一次是1for (int i = 0; i < size - gap; i++){int end = i;int tmp = arr[end + gap];while (end >= 0){if (arr[end] > tmp){arr[end + gap] = arr[end];}else{break;}end-=gap;}arr[end + gap] = tmp;}}
}

按照每次/3减小是最合理的；for循环i每次加一，代表一次for循环包含当前gap下的所有的预排序；

###时间复杂度：O（N^1.3）

五、堆排

//向下调整
void AdjustDown(int* arr, int parent, int size)
{int child = parent * 2 + 1;while (child < size){if (child + 1 < size && arr[child] < arr[child + 1]){child++;}if (arr[parent] < arr[child]){swap(arr[child], arr[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}
//堆排
void HeapSort(int* arr, int size)
{//建堆for (int i = (size - 1 - 1) / 2; i >= 0; i--){AdjustDown(arr, i, size);}//O(N)//开始排序for (int i = size - 1 ; i >= 0; i--){swap(arr[0], arr[i]);AdjustDown(arr, 0, i - 1);}//O(N*logN)
}

###时间复杂度是O（N*lonN）

六、快速排序

1、hoare：

###思路：

选取一个基准值，这里选取最左边的值；从前后分别遍历数据；先从后面走起，碰见比基准值小的就停止；前面的begin碰到比基准值大的就停止；两者都停了就交换，把大的换到后面，小的换到前面；最后end和begin相遇，相遇的位置一定是比基准值小的值，跳出循环，交换基准值和begin位置的值；那么keyi之前的值就都是比它小的，后面就都是比它大的；利用keyi的位置将数据分割成两部分，利用递归，这两部分再次进行相同的操作；（似于二叉树结构）

为什么begin和end相遇的位置的值一定小于等于基准值的？因为是让end先走的，end是要找小于基准值的位置，这里分析begin和end相遇的几种情况：情况一，end找不到比基准值小的，那么最后相遇的位置就是基准值的位置，跳出循环，自己和自己交换，递归右边的部分；情况二：begin和end已经交换过了但还没相遇，end走，找不到小于基准值的值，最后和begin相遇，而begin的值是上一次和end交换的，一定是小于基准值的值；情况三：end找到了比基准值小的，停止，begin开始找比基准值大的，找不到，最后和end相遇，而end处的值就是小于基准值的，跳出交换；所以让end先走，先找小就能保证相遇的位置一定是比基准值小的。

###代码：

void QuickSort1(int* arr, int left, int right)
{int keyi = left;int begin = left;int end = right;while (begin < end){while (begin < end && arr[end] >= arr[keyi]){end--;}//先走右边保证最后交换的位置比arr[keyi]小while (begin < end && arr[begin] <= arr[keyi]){begin++;}swap(arr[begin], arr[end]);}swap(arr[keyi], arr[begin]);keyi = begin;QuickSort1(arr, left, keyi - 1);QuickSort1(arr, keyi + 1, right);
}

###时间复杂度：O（N*logN）；分析：每一次遍历完就是N，begin和end相遇，那么两者共同走完了整段数据；而这个递归是类似于二叉结构的，就是logN；

但是还有优化的空间：

1、当某一段数据很少时，使用递归反而不好，此时用插入排序处理（杀鸡焉用牛刀，很少的数据不需要用堆排、希尔，但是要从一般效率的排序中选一个最好的就是插入排序），这样就有优化效果；

2、当数据是接近有序时，每一次分割之后，前面的没有数据，后面数据量是开始的数据-1；也就是keyi最后每次都是在开始的位置，那么就达不到 logN的效果，此时高度是N，因为每一次都是减少一个，而不是像一般情况小类似于每次折半；所以最后的时间复杂度是O（N^2）；此时效率太低了；为了解决，这里使用三数取中，就是每次进行单趟排序时，先取一个值放在left的位置 ,这个数是left处、right处、以及两者中间处数据中中间大小的那个值；这样一来keyi处的值就不会是最小的，那么排序一次之后keyi也不会是在最开头，那么又变成了类似二叉结构的情况；达到了优化的效果。

###代码：

//快排三数取中
int GetMid(int* arr, int left, int right)
{int midi = (right + left) / 2;if (arr[left] > arr[midi]){if (arr[midi] > arr[right]){return midi;}else if (arr[left] > arr[right]){return right;}else{return left;}}else//arr[left]<=arr[midi]{if (arr[right] > arr[midi]){return midi;}else if (arr[left] > arr[right]){return left;}else{return right;}}
}
//快排
//hoare
void QuickSort1(int* arr, int left, int right)
{if (right - left + 1 <= 10)//小区间优化{InsertSort(arr, right - left + 1);return;}//三数取中if (left >= right){return;}int midi = GetMid(arr, left, right);swap(arr[midi], arr[left]);int keyi = left;int begin = left;int end = right;while (begin < end){while (begin < end && arr[end] >= arr[keyi]){end--;}//先走右边保证最后交换的位置比arr[keyi]小while (begin < end && arr[begin] <= arr[keyi]){begin++;}swap(arr[begin], arr[end]);}swap(arr[keyi], arr[begin]);keyi = begin;QuickSort1(arr, left, keyi - 1);QuickSort1(arr, keyi + 1, right);
}

2、挖坑法：

###思路：

相同地，取一个基准值，这个基准值处就是挖了一个坑；这里取最左边地的数据，那么从后面开始找，找到比基准值小的就把这个值放在坑的位置，那么这个比基准值小的数据的位置又形成了一个坑，从前面开始找找到比基准值大的值就把这个值放在上次的坑处，最后end和begin相遇，相遇得到位置也是一个坑，最后把基准值放在这个坑处；这样，也能达到排序效果；这个方法的优点在于它很自然，在前面挖了坑，就从后面找，后面挖了坑就从前面找；

3、前后指针法：

###思路：

利用两个指针，第一个指针prev指向开始的位置，第二个指针cur指向prev的下一个位置；基准值还是取最左边的，cur找到比基准值小的就让prev加加，然后cur和prev处的值进行交换，最后cur走到空，跳出循环，交换keyi处的值和prev处的值，prev处的一定是小于基准值的；这样也能把大的值放到后面，小的放在前面；最后进行分割递归；

###代码：

//前后指针法
void QuickSort2(int* arr, int left, int right)
{if (right - left + 1 <= 10){InsertSort(arr, right - left + 1);return;}if(left >= right){return;}int midi = GetMid(arr, left, right);swap(arr[midi], arr[left]);int prev = left;int cur = prev + 1;int keyi = left;while (cur <= right){if (arr[cur] < arr[keyi] ){prev++;swap(arr[cur], arr[prev]);}cur++;}swap(arr[keyi], arr[prev]);keyi = prev;QuickSort2(arr, left, keyi - 1);QuickSort2(arr, keyi + 1, right);
}

 4、快排非递归

###原因：

递归深度太深不好，函数栈帧在栈区，而给非递归使用数据结构的栈在堆，堆区远大于栈区；

###思路：

将递归转到非递归使用数据结构栈；将每次一单趟排序的区间前后界限值放进栈，先放后面的界限；每一次排序之后进行分割，再放分割之后的界限值；当界限之间的数据小于两个时不需要进栈；最后达到有序；

//非递归快排实现
int quick(int* arr, int left, int right)//单趟
{int prev = left;int cur = prev + 1;int keyi = left;while (cur <= right){if (arr[cur] < arr[keyi]){prev++;swap(arr[prev], arr[cur]);}cur++;}swap(arr[prev], arr[keyi]);return prev;
}
void QuickSort3(int* arr, int size)
{stack<int> st;st.push(size-1);st.push(0);while (!st.empty()){int left = st.top();st.pop();int right = st.top();st.pop();int keyi = quick(arr, left, right);//分割if (keyi + 1 < right)//进入单趟排序的至少得有两个数才有意义{st.push(right);st.push(keyi + 1);}if (keyi - 1 > left){st.push(keyi - 1);st.push(left);}}
}

七、归并排序

###思路：

将数据分为两部分，这两部分是有序的，再遍历这两部分，创建一个新的数据，将小的放在新的数组里面，直到遍历完；

问题是如何保证分割的两部分是有序的：将数据继续划分直到只有一个数据，一个数据没有比较的对象那么它就是有序的，这一个数据和另一个数据进行归并，形成有序的两个数据；这样依次让1归并的每组数据量增多，最后就是整组数据被分为有序的两部分进行归并那么最后就排好序了。

1、递归写法：

这里类似于后序思想，先划分数据，直到划分到一个数据时回退开始归并；

###代码：

void _MergeSort(int* arr, int* tmp, int left, int right)
{if (left >= right){return;}int midi = (left + right) / 2;_MergeSort(arr, tmp, left, midi);_MergeSort(arr, tmp, midi + 1, right);int begin1 = left, end1 = midi;int begin2 = midi + 1, end2 = right;int i = left;while (begin1 <= end1 && begin2 <= end2){if (arr[begin1] <= arr[begin2]){tmp[i++] = arr[begin1++];}else{tmp[i++] = arr[begin2++];}}while (begin1 <= end1){tmp[i++] = arr[begin1++];}while (begin2 <= end2){tmp[i++] = arr[begin2++];}memcpy(arr + left, tmp + left, sizeof(int) * (right - left + 1));
}
void MergeSort(int* arr, int size)
{int* tmp = new int[size];int left = 0, right = size - 1;_MergeSort(arr, tmp,left, right);delete[] tmp;tmp = nullptr;
}

2、非递归写法：

这里不能使用栈了，因为这里有回退时使用区间的过程，若是使用栈，归并时找不到区间，除非使用两个栈，一个用于记录区间方便最后进行归并，另一个进行区间划分；

这里使用循环，利用一个gap值，gap最开始是1，代表一个数据，一个gap组有两个数据，这两个数据进行归并；gap每次都乘二，第二次每个gap组有四个数据，两两归并；依次增加gap，直到gap和数组大小相同时停止；

注意的问题：当数据个数不是2的次方个时，进行归并时可能数组会越界；此时要加判断，若是begin2越界了，那么说明此次归并的后面一半数据不需要归并了，前面的已经是有序的，后面的越界了；当end2越界时，将end2置为size-1，因为后面一半数据begin2没有越界只是end2越界了，说明后面一半数据中有的需要和前面一半数据进行归并，j将end2置为size-1，使得归并的区间合法；将begin2的判断放在end2的前面，因为当begin2越界了时，end2一定越界，此时直接break就行了。

###代码：

void MergeSortNonR(int* arr, int size)
{int gap = 1;int* tmp = new int[size];while (gap < size){for (int i = 0; i < size; i += 2 * gap){int begin1 = i, end1 = begin1 + gap - 1;int begin2 = i +gap, end2 = begin2 + gap - 1;int j = i;if (begin2 >= size){break;}if (end2 >= size){end2 = size - 1;}while (begin1 <= end1 && begin2 <= end2){if (arr[begin1] <= arr[begin2]){tmp[j++] = arr[begin1++];}else{tmp[j++] = arr[begin2++];}}while (begin1 <= end1){tmp[j++] = arr[begin1++];}while (begin2 <= end2){tmp[j++] = arr[begin2++];}memcpy(arr + i, tmp + i, sizeof(int) * (end2 - i + 1));}gap *= 2;}
}

八、计数排序

###思路：

通过创建一个数组，这个数组是原数据的映射；统计相同元素出现次数，根据统计结果依次将数据放回原数组中；

###代码：

//计数排序
void CountSort(int* arr,int size)
{int max = arr[0], min = arr[0];for (int i = 1; i < size; i++){if (arr[i] <= min){min = arr[i];}if (arr[i] >= max){max = arr[i];}}int range = max - min + 1;int* count = (int*)calloc(range, sizeof(int));for (int i = 0; i < size; i++){count[arr[i] - min]++;}int j = 0;for (int i = 0; i < range; i++){while (count[i]--){arr[j++] = i + min;}}
}

九、排序的时间复杂度和空间复杂度以及稳定性

	时间复杂度	空间复杂度	稳定性
冒泡排序	O(N^2)	O(1)	稳定
选择排序	O(N^2)	O(1)	不稳定
插入排序	O(N^2)	O(1)	稳定
希尔排序	O(N^1.3)	O(1)	不稳定
推排序	O(NlogN)	O(1)	不稳定
快速排序	O(NlogN)	O(logN)	不稳定
归并排序	O(NlogN)	O(N)	稳定
计数排序	O(N+range)	O(range)	无

1、稳定性：

两个相同元素在排序前后的相对顺序不变：比方说两个相同的数，其中一个在另一个前面，排序完之后，这个在前面的数依旧是在前面的；符合这种情况就是稳定了，否则就不稳定；

使用场景：对于单调的整形没有意义，因为数都一样；对于包含多个属性的对象进行排序，假定一个属性已经排好了，排其他属性时这个排号的属性不受影响；

分析这八个排序：

1. 对于冒泡排序，若前一个比后一个大就交换，当两个数相同时，不交换，也就是说排序前后的相同元素的相对顺序不变；
2. 对于选择排序，假设开始的位置的数据和中间有的数据相同，当找到最小和开始的交换时，可能会改变相同数据的相对顺序；比如6 ，2，6，6，1，9；循环一次，开始的6成了最后的6；
3. 插入排序，假定前面的有序，当一个元素和前面的比较，遇到相同元素时插入到这个相同元素的后面，未改变相对位置；
4. 希尔排序预排序可能会改变相同元素的相对位置；
5. 堆排序，举个极端例子：假设数据全部相同，那么排序一次，开始位置的数据就放到最后了；
6. 快排，swap keyi位置和后面的begin位置时可能会改变顺序；时间复杂度是因为开辟栈帧，每层开辟一个；
7. 归并：两个相同数据，前面的小于或者等于先放入新数组；
8. 计数排序：时间复杂度看最后放数据的循环，外层是range，遍历完range，内层是每个range上不为0的，内层总共走size次，那么就是range+size；计数排序只针对单调的数据，所以不涉及到稳定性。