您现在的位置是：首页 >学无止境 >数据结构：排序—交换排序（三）网站首页学无止境
数据结构：排序—交换排序（三）
一、交换排序
基本思想：所谓交换，就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置。
交换排序的特点：将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动。
1、冒泡排序
这时在我们学习这些不同的排序算法之前最常使用的排序方法，在这里我们就不过多进行讲解了。
public static void bubbleSort(int[] arr){
for (int i = 0; i < arr.length-1; i++) {
boolean flg = false;
for (int j = 0; j < arr.length-1-i; j++) {
if(arr[j] > arr[j+1]){
swap(arr,j,j+1);
flg = true;
}
}
if(!flg){
break;
}
}
}2、快速排序
快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法，其基本思想为：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。
而我们的区间按照基准值划分为左右两半部分的常见方式有：
（1）Hoare版
首先，我们选定要排序的数据第一个元素为基准值，然后利用两个指针:left和right,让left指向第一个元素，right指向最后一个元素，而此时我们的基准值tmp就是我们left位置的值，之后我们开始移动left和right，如果此时right的值，大于等于我们的tmp，就让right--往前走，直到遇到小于tmp的值或left和right相遇停止，之后让left移动，如果小于等于我们的tmp，就让left++往后走，直到遇到大于tmp的值或left和right相遇停止，然后交换此时left和right指向的这两个值，直到left和right相遇，并让left的值与第一个元素进行交换，同时返回此时的left或right的位置，此时我们就能发现我们返回后的位置左边全是小于他的，右边全是大于他的，这之后我们再以他为分界，去递归他的左边和右边重复上面的操作。
注意：这里我们一定要让right先走，然后再让left走，因为如果我们让left先走的话就会可能让大于基准值的元素和第一个元素交换，交换完后发现左边第一个元素非但没有变小反而变大了。
public static void quickSort(int[] arr){
quick(arr,0,arr.length-1);
}
private static void quick(int[] arr, int start, int end) {
if(start >= end){
return;
}
int par = partitionHoare(arr,start,end);
quick(arr,start,par-1);
quick(arr,par+1, end);
}
public static int partitionHoare(int[] arr,int left,int right){
int i = left;
int tmp = arr[left];
while(left < right){
while(left < right && arr[right] >= tmp){
right--;
}
while(left < right && arr[left] <= tmp){
left++;
}
swap(arr,left,right);
}
swap(arr,left,i);
return left;
}（2）挖坑版
我们依然将第一个元素作为一个基准值，并且还是像上面一样后面找小于他的元素，左边找大于他的元素，但是这回我们不将他进行交换，而是每遇到小于他的元素，就更新left位置的值，每遇到大于他的元素，就更新right位置的值,直到left和right相遇，然后将此时left位置的值更新为我们的基准值，并返回left。
public static void quickSort(int[] arr){
quick(arr,0,arr.length-1);
}
private static void quick(int[] arr, int start, int end) {
if(start >= end){
return;
}
int par = partition(arr,start,end);
quick(arr,start,par-1);
quick(arr,par+1, end);
}
public static int partition(int[] arr,int left,int right){
int tmp = arr[left];
while(left < right){
while (left < right && arr[right] >= tmp){
right--;
}
arr[left] = arr[right];
while(left < right && arr[left] <= tmp){
left++;
}
arr[right] = arr[left];
}
arr[left] = tmp;
return left;
}（3）前后指针版
首先我们设立两个指针prev指向left位置，cur指向left+1位置，之后我们判断cur的元素是否小于基准值left位置的元素，并且prev的下一个是否等于cur，如果cur的元素小于我们的基准值并且prev的下一个不等于cur,就把cur和prev的元素进行交换。否则cur++往后走，然后不断循环直到cur大于right,我们就把prev和left位置的值进行交换。
public static void quickSort(int[] arr){
quick(arr,0,arr.length-1);
}
private static void quick(int[] arr, int start, int end) {
if(start >= end){
return;
}
int par = partition2(arr,start,end);
quick(arr,start,par-1);
quick(arr,par+1, end);
}
public static int partition2(int[] array, int left, int right) {
int prev = left ;
int cur = left+1;
while (cur <= right) {
if(array[cur] < array[left] && array[++prev] != array[cur]) {
swap(array,cur,prev);
}
cur++;
}
swap(array,prev,left);
return prev;
}3、快速排序的优化
当我们使用快速排序的时候，我们可能在排序的过程中，就已经将他排好序了，但是由于我们的排序过程还为结束，这样就会导致大量的计算，因此我们需要将这种情况进行优化
（1）三数取中法
所谓三数取中法，就是得到left,right和mid的值，然后比较他们三个的值，得到他们三个的中位数，并返回然后和我们的第一个位置与中位数的位置的值进行交换，然后这里第一个位置就是我们的基准值了，这样我们就可以发现即使是，已经排好序的，依然可以像之前的方式进行排序，不用大量的重复计算了。
那么我们该怎样取得中位数呢？这就得到了两种情况了，而每种情况又分为三个情况
第一种：arr[left] < arr[right]
（1）arr[mid] < arr[left]
此时mid的值比left还小，我们的left就是我们的中位数
（2）arr[mid] > arr[right]
此时mid的值比right还大，我们的right就是我们的中位数
（3）除上述两个情况外，此时mid就是我们的中位数
第二种：arr[left] > arr[right]
（1）arr[mid] > arr[left]
此时mid的值比left还大，我们的left就是我们的中位数
（2）arr[mid] < arr[right]
此时mid的值比right还小，我们的right就是我们的中位数
（3）除上述两个情况外，此时mid就是我们的中位数
public static void quickSort(int[] arr){
quick(arr,0,arr.length-1);
}
private static void quick(int[] arr, int start, int end) {
if(start >= end){
return;
}
//三数取中法
int index = midNum(arr,start,end);
swap(arr, start, index);
int par = partition(arr,start,end);
quick(arr,start,par-1);
quick(arr,par+1, end);
}
public static int midNum(int[] arr,int left,int right){
int mid = (left+right)/2;
if(arr[left] < arr[right]){
if(arr[mid] < arr[left]){
return left;
}else if(arr[mid] > arr[right]){
return right;
}else{
return mid;
}
}else{
if(arr[mid] > arr[left]){
return left;
}else if(arr[mid] < arr[right]){
return right;
}else{
return mid;
}
}
}
public static int partition(int[] arr,int left,int right){
int i = left;
int tmp = arr[left];
while(left < right){
while (left < right && arr[right] >= tmp){
right--;
}
arr[left] = arr[right];
while(left < right && arr[left] <= tmp){
left++;
}
arr[right] = arr[left];
}
arr[left] = tmp;
return left;
}（2）递归到小的子区间
我们知道，当我们在不断排序的过程中后，我们排序的数据越来越趋于有序，而我们在插入排序中曾提到过，当我们的数据越有序的时候，我们的直接插入排序的效率越高，所以当我们在递归到一定小区间的时候我们就可直接使用直接插入排序，来提高效率，减少内存。
public static void quickSort(int[] arr){
quick(arr,0,arr.length-1);
}
private static void quick(int[] arr, int start, int end) {
if(start >= end){
return;
}
if(start-end+1<10){
insertSort(arr);
}
int par = partition(arr,start,end);
quick(arr,start,par-1);
quick(arr,par+1, end);
}
public static void insertSort(int[] arr){
for (int i = 1; i < arr.length; i++) {
int tmp = arr[i];
int j = i-1;
for (; j >= 0; j--) {
if(arr[j] > tmp){
arr[j+1] = arr[j];
}else{
break;
}
}
arr[j+1] = tmp;
}
}
public static int partition(int[] arr,int left,int right){
int i = left;
int tmp = arr[left];
while(left < right){
while (left < right && arr[right] >= tmp){
right--;
}
arr[left] = arr[right];
while(left < right && arr[left] <= tmp){
left++;
}
arr[right] = arr[left];
}
arr[left] = tmp;
return left;
}4、快速排序非递归实现
首先我们先利用挖坑版的方法取得的mid位置。
然后我们判断mid的左右两边是否存在两个或以上的元素，如果mid > left+1，代表左边有两个或以上的元素，将他左边第一个元素和mid的左边元素放入栈中，如果mid < right-1，代表右边有两个或以上的元素，将他mid的右边边元素和最后一个元素放入栈中。
之后，我们进行出栈，我们按照我们的入栈顺序，可以得到，当我们出栈的时候，我们的栈顶元素就是我们左右两边这部分的元素的最后一个元素，下一个出栈的就是我们左右两边这部分的元素的第一个元素。并将这两个元素，传入挖坑法中进行排序的到新的mid。
最后，再次进行mid左右两边的判断和入栈，然后利用循环重复上面的出栈操作，直到栈为空，我们就成功的排好序了。
public static void quickSortNonR(int[] arr){
Stack<Integer> stack = new Stack<>();
int left = 0;
int right = arr.length-1;
int mid= partition(arr,left,right);
if(mid > left+1){
stack.push(left);
stack.push(mid-1);
}
if(mid < right-1){
stack.push(mid+1);
stack.push(right);
}
while(!stack.isEmpty()){
right = stack.pop();
left = stack.pop();
mid= partition(arr,left,right);
if(mid > left+1){
stack.push(left);
stack.push(mid-1);
}
if(mid < right-1){
stack.push(mid+1);
stack.push(right);
}
}
}
public static int partition(int[] arr,int left,int right){
int i = left;
int tmp = arr[left];
while(left < right){
while (left < right && arr[right] >= tmp){
right--;
}
arr[left] = arr[right];
while(left < right && arr[left] <= tmp){
left++;
}
arr[right] = arr[left];
}
arr[left] = tmp;
return left;
}好了，今天的分享就到这里了，还请大家多多关注，我们下一篇见！
站长推荐
- U8W/U8W-Mini使用与常见问题解决
U8W/U8W-Mini使用与常见问题解决 - 分享几个国内免费的ChatGPT镜像网址(亲测有效)
分享几个国内免费的ChatGPT镜像网址(亲测有效) - stm32使用HAL库配置串口中断收发数据（保姆级教程）
stm32使用HAL库配置串口中断收发数据（保姆级教程） - QT多线程的5种用法，通过使用线程解决UI主界面的耗时操作代码，防止界面卡死。
QT多线程的5种用法，通过使用线程解决UI主界面的耗时操作代码，防止界面卡死。... - SpringSecurity实现前后端分离认证授权
SpringSecurity实现前后端分离认证授权