九大排序之交换排序

1.前言

所谓交换，就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置，交换排序的特点是：将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动。

重点：

冒泡排序和快速排序

2.冒泡排序

思路：冒泡排序是典型的交换排序，每趟排一个值，一直排n-1趟，这样就能把n个值按照一定的顺序排好。

end记录冒泡的最终位置；
待排区间中的数据前后两两比较，交换，冒泡到end；
如果在一趟比较中没有发生交换则提前结束循环；
–end，准备冒下一个泡。当end > 0时循环继续。

代码如下：

void Bubble(int* arr,int size)
{//1.先确定趟数int end=size-1;while(end>0){bool exchange=false;for(int i=1;i<=end;i++){if(arr[i]<arr[i-1]) {exchange=true;swap(&arr[i],&arr[i-1]);}}end--;if(exchange) break;}
}

动画演示如下：

冒泡排序总结：

时间复杂度：O(n)~O(n^2)

空间复杂度:O(1)

稳定性：稳定

3.快速排序

快排是hore在19世纪提出的一种基于二叉树结构的排序方法，其基本思想是：先选定基准值，然后比基准值的小的放在其左边，比基准值大的放在其右边。然后再进行递归左边的值，然后再进行递归右边的值。一直递归到只有一个值为止。

方法一左右指针法也称hore法：

1. 选择一个关键字key，一般选最左值或最右值。
2. 单趟排序：目的是利用基准值key将序列分成左右两个部分：key左边的值比key要小，右边的值比key要大。即直接将key移动到排序后的最终位置。
3. 递归思想：单趟排完，再使用同样的方法使得左子区间有序，右子区间也有序，整体就有序了。

void QuickSort(int* arr,int left,int right)
{if(left>=right) return;int mid=parition(arr,left,right);QuickSort(arr,left,mid-1);QuickSort(arr,mid+1,right);
}int parition(int* arr,int left,int right)
{int keyi=arr[left];while(left<right){while(left<right&&keyi<=arr[right]) right--;while(left<right&&keyi>=arr[left])  left++;swap(&arr[left],&arr[right]);}swap(&keyi,&arr[left]);return left;
}

动画演示：

规律总结：

选最左值做key，右边先走：左右相遇时比key小
选最右值做key，左边先走：左右相遇时比key大

为什么？
没有相遇之前谁先走都无所谓，L找大R找小
相遇时（key选最左），无非是 L<–R 或 L–>R

L<-R （R找不到小），由于上次交换后L还未发生移动，此时的L< key (或L == key，其余所有数都比key要大)；

例：5 6 3 1 7 4 2 8 9 ---如果是左边先走那么最后一次交换是 5 2 3 1 4 7 6 8 9 left和right同时指向7所在的位置，又因为选择了左边做基准值，所以相遇的位置必须是比基准值小的，那么就只能右边先走，把所有的大的走完了，遇见的第一个比基准值小的就是相遇值。
L->R（L找不到大），由于是每次循环R先走，此时的R<key；(与上述同理)

方法二:前后指针法

1.定义两个指针（下标）cur与prev一前一后：prev指向left，cur指向left+1；
2.选最左端left做keyi；（需提前做三数取中优化：让left,mid,right三个数的中间值于left交换）；
3.cur不断向前找小于key的数，找到后与++prev(大于key)交换；如果++prev==cur，则可以不交换。
经4.过这样的交换，prev左边的值 (keyi, prev] 都小于key，prev右边的值 (prev, cur)都大于等于key。（prev是左右区间的交界）
5.最后将prev和key交换，就可以实现快排单趟的分割。

代码如下：

//三数取中
int GetMidIndex(int *arr, int left, int right){int mid = left + (right - left) / 2;int tmp1 = arr[left] > arr[mid] ? left : mid;int tmp2 = arr[mid] > arr[right] ? mid : right;return arr[tmp1] > arr[tmp2] ? tmp2 : tmp1;}int Partion2(int *arr, int left, int right){//三数取中 -- 有序的情况每次二分，将最坏情况变成最好情况int midi = GetMidIndex(arr, left, right);Swap(&arr[midi], &arr[left]);int prev=left,cur=left+1;while(cur<=right){if(arr[cur]<arr[midi]&&prev+1!=cur){prev++;swap(&arr[prev],&arr[cur]);}cur++;}swap(&arr[midi],&arr[prev]);return prev;
}void QuickSort(int *arr,int left,int right)
{if(left>=right) return;int mid=Parition2(arr,left,right);QuickSort(arr,left,mid-1);QuickSort(arr,mid+1,right);
}

关键点：这里是把三数取中的值，与最左边进行了互换，所以选取的是最左边作为关键值。

当选取左边为关键值时：

1.prev=left,cur=left+1(把基准值排除在外)

2.循环条件是 cur<=right

3.最后把基准值与prev的值进行交换(得到了左边比其小，右边比其大)

当选取右边为关键值时：

1.那么cur应该为cur=left,prev=left-1;

2.cur<right(把基准值排除在外)

3.最后把基准值与prev的值进行交换

方法三:挖洞法

挖洞法的中心思想就是，把基准值挖掉，用一个数记录下来，然后左边找比他大的，右边找比他小的，填到洞里面，然后找到的那个就是一个新的洞

int Partion3(int *arr, int left, int right){//三数取中 -- 将有序的最坏情况变成最好情况int midi = GetMidIndex(arr, left, right);Swap(&arr[midi], &arr[left]);int tmp = arr[left];int hole = left;while (left < right){//右边找小，放到左边的坑while (arr[right] >= key && left < right){right--;}arr[hole] = arr[right];hole = right;//左边找大，放到右边的坑while (arr[left] <= key && left < right){left++;}arr[hole] = arr[left];hole = left;}arr[hole] =tmp;return hole;
}

动画如下：

快速排序的特性总结：
1. 快速排序整体的综合性能和使用场景都是比较好的，所以才敢叫快速排序
2. 时间复杂度：O(N*logN)~O(N^2)
3. 空间复杂度：O(logN)~O(N)（栈结构消耗）
4. 稳定性：不稳定---排序主要依靠的是选基准值。如果每次选的基准值都是最大的，那就是O（n^2）
5. 数据敏感性：敏感，越无序效率越高

快排的复杂度和优化分析

复杂度：

如果每次选取的基准值都是中间值的话，那么就会形成一棵二叉树

那么时间复杂度就是O(N*logN),空间复杂度就是O(logN）

如果每次排序的话选取的基准值都是最大值的话，那么就无法形成两端区间。

那么时间复杂度就是0（N*2）,空间复杂度也是O（N）

如果数据太多，会因此调用堆栈空间太多，而导致栈溢出。

优化：

1.发现时间和空间复杂度都与基准值的选取有关，那么就可以利用三数取中的方式，来尽量找到一个中间值，使其成为一棵二叉树

2.当快排分割区间分割到一定的程序的时候，试试用直接插入排序来对这段区间排序，减少递归的次数

快排的缺陷

无法解决值相等或者重复序列排序的问题