抬头仰望星空,是否能发现自己的渺小。

伪斜杠青年

人们总是混淆了欲望和理想

基本排序 – 快速排序

算法基本思想:

实现快速排序符法的关键在于先在数组中选择一个数字, 接下来把数组中的数字分为两部分, 比选择的数字小的数字移到数组的左边, 比选择数的字大的数字移到数组的右边。

具体方法:

将取的随机数(基准数)固定为左边第一个

相关信息:

如果每次基准值为需要排序的子串中的中间值,这样就把原来的子序列分解成了两个长度基本相等的更小的子序列,则最好的时间复杂度为O(nlog2n)

如果每次选取的基准值为最小数,它把原来的序列分解成一个空序列和一个长度为原来序列长度减1的子序列,最坏为O(n2)

排序过程中存在大量交换,相同数字的前后位置交换可能性比较大,为不稳定算法

代码实现:

private static void quickSort(int[] num, int left, int right) {
if (left > right) {
//结束条件
return;
}
//基准值
int pivot = num[left];
int i = left;
int j = right;

while (i < j) {

//从右往左找比基准值小的数字
while (pivot <= num[j] & i < j) {
j--;
}
//从左往右找比基准值大的数字
while (pivot >= num[i] & i < j) {
i++;
}

//如果比基准值大的数字在左边 比基准值小的数字在右边 则交换他们
if (i < j) {
int temp = num[i];
num[i] = num[j];
num[j] = temp;
}
}

//将基准值与小的数字交换 因为ij已交换 所以此时i为小值
num[left] = num[i];
num[i] = pivot;
//递归排序左边元素
quickSort(num, left, i - 1);
//递归排序右边元素
quickSort(num, i + 1, right);
}

时隔一年,快排看上去已经很清晰明了了,记得以前不知道怎么像没开光一样无法理解。

可以看以前写的一篇文章:点我

本算法推荐图文:点我

另一种实现方式

思路:与上面一样 只是换个写法

代码实现:

private static void quickSort(int[] arr, int left, int right) {
//基本条件
if (left < right) {
//获取基准值 将数组分为两部分
int pivot = partition(arr, left, right);
//递归排序左边元素
quickSort(arr, left, pivot - 1);
//递归排序右边元素
quickSort(arr, pivot + 1, right);
}
}

private static int partition(int[] arr, int left, int right) {
//记录基准值
int pivot = arr[left];
while (left < right) {
//从右往左找比基准值小的数字
while (left < right && arr[right] >= pivot) {
--right;
}
//将比基准值小的数字与基准值交换
arr[left] = arr[right];
//从左往右找比基准值大的数字
while (left < right && arr[left] <= pivot) {
++left;
}
//将比基准值大的数字 和找出来的 比基准值小的数字交换
arr[right] = arr[left];
}
//扫描完成,将基准值放到之前找到的比基准值大的数字位置上 注:此时left在while循环中已变更
arr[left] = pivot;
//返回下一个基准值位置
return left;
}

哪个容易理解看哪个。推荐文章:一个非常好的文章 图文 PS:实际上我就是这里Copy的~


0条评论

发表评论