学校信息门户网站建设,国内做设计的网站有哪些方面,推广类软文案例,合肥网站设计建设公司1.介绍 快排分为两种: 1.lomuto分区算法 (快慢指针)(单边) 2.Hoare分区算法 (前后指针)(双边)
快排主要思想:选一个基准元素分为两部分,先让左边排一下序再让右边排序
2.思路分析
1.lomuto分区算法
默认#xff1a;最右边的元素作为基准点
1.设置两个指针(dest , cu…1.介绍 快排分为两种: 1.lomuto分区算法 (快慢指针)(单边) 2.Hoare分区算法 (前后指针)(双边)
快排主要思想:选一个基准元素分为两部分,先让左边排一下序再让右边排序
2.思路分析
1.lomuto分区算法
默认最右边的元素作为基准点
1.设置两个指针(dest , cur)通过使用dest找比基准点大的cur找比基准点小的
2.当同时停下并且不相等进行交换这样会达到一种dest是比基准点小的分界点左边全是比基准点小的走到最后一步只需要与基准点交换即可。遍历序列并交换元素从序列的第一个元素开始逐个与基准元素进行比较将小于等于基准元素的元素交换到序列的左侧。
3.更新基准元素位置遍历完成后将基准元素交换到正确的位置上使得基准元素左侧的元素都小于等于它右侧的元素都大于它。
4.分治递归对基准元素左右两侧的子序列分别重复以上步骤直到每个子序列只剩下一个元素或为空。
平均复杂度:O(nlogn)
最坏情况:O(n^2)
2.分析普通快排存在的缺点 1.在最坏情况下即每次划分都导致一个子序列为空 我们可以通过随机基准点进行优化以防止出现这种情况 2.数据量很少的时候快排并不有优势反倒不如插入排序所以我对其进行了当元素小于10时候我就使用插入排序。
3.Hoare分区算法 默认: 最左边的元素为基准点
注意点:一定要先移动右指针在移动左指针因为右指针找是比基准点小的谁先走就意味着最后一轮谁过后谁先移动去找另一个而右指针最后一次交换存的是比基准点大的左指针是比基准点小的要是先移动左指针就会使一个比基准点大的元素放在基准点前面 3.代码实现
1.lomuto分区算法 /**实现快速排序(单边循环)** lomuto快速排序* */public class sortTest9 {private int[] data;public void sort(int[] data){this.data data;dfs(0,data.length - 1);}private void dfs(int start, int end) {//分区的时候只有一个元素结束递归if (start end) return;//分区(已基准点分区)int j partition(start,end);//左分区dfs(j - 1, end);//右分区dfs(start, j 1);}private int partition(int start, int end) {//定义基准数int prev data[end];int less start;//慢指针int great start;//快指针for (; great end - 1; great) {if (data[great] prev){//防止无意义的空交换if (great ! less) swap(data,less,great);less;}}//到最后交换基准数(也就是end的值)和慢指针less的值swap(data,less,end);//慢指针所在的位置就是分区的位置return less;}private void swap(int[] data, int less, int great) {int temp data[less];data[less] data[great];data[great] temp;}
}
2.Hoare分区算法 /**实现快速排序(双边循环)** */public class sortTest10 {private int[] data;public void sort(int[] data){this.data data;dfs(0,data.length - 1);}private void dfs(int start, int end) {int i start;int j end;//定义基准数int prev data[start];if (i j){return;}//处理重复元素(相等的也交换)并且双指针都移动while(i ! j){//后指针找比基准数小的while(true) {//等于不等于都一样(基准数左边可以含有等于基准点的数右边也可以)if (i j data[j] prev) {break;}j--;}//前指针找比基准数大的while(true){if (i j data[i] prev) break;i;}swap(i,j);j--;i;}//确定了两指针指向头一个与基准数交换swap(j,start);//左分区swap(start,j - 1);//右分区swap(j 1,end);}//用来交换元素private void swap(int less, int great) {int temp data[less];data[less] data[great];data[great] temp;}
}3.缺点优化 1.随机基准点 2.处理重复元素 3.当递归到元素小于10的时候转为插入排序
import java.util.Arrays;
import java.util.Random;public class sortTest11 {private static final int INSERTION_SORT_THRESHOLD 10;public static void quickSort(int[] array) {quickSort(array, 0, array.length - 1);}private static void quickSort(int[] array, int start, int end) {if (start end) {// 当元素个数小于等于阈值时使用插入排序if (end - start 1 INSERTION_SORT_THRESHOLD) {insertionSort(array, start, end);} else {// 随机选择基准值并进行划分int pivotIndex randomPartition(array, start, end);// 对基准值左侧的子数组递归排序quickSort(array, start, pivotIndex - 1);// 对基准值右侧的子数组递归排序quickSort(array, pivotIndex 1, end);}}}private static int randomPartition(int[] array, int start, int end) {int randomIndex new Random().nextInt(end - start) start;swap(array, randomIndex, start);return partition(array, start, end);}private static int partition(int[] array, int start, int end) {int pivot array[start];int left start 1;int right end;while (left right) {while (left right array[left] pivot) {left;}while (left right array[right] pivot) {right--;}if (left right) {swap(array, left, right);left;right--;}}swap(array, start, right);return right;}private static void insertionSort(int[] array, int start, int end) {for (int i start 1; i end; i) {int key array[i];int j i - 1;while (j start array[j] key) {array[j 1] array[j];j--;}array[j 1] key;}}private static void swap(int[] array, int i, int j) {int temp array[i];array[i] array[j];array[j] temp;}
}
