快速排序的相关算法题（java）

程序员徐公

发布于 2018-09-18 17:07:01

5740

发布于 2018-09-18 17:07:01

文章被收录于专栏：程序员开发工具程序员开发工具

快速排序的相关算法题（java）

关于二分查找的，可以参考我的这篇博客二分查找的相关算法题

关于归并排序的的，可以参考我的这篇博客归并排序递归版和非递归版的实现（java）

关于快速排序的，可以参考我的这篇博客?快速排序的相关算法题（java）

转载请注明原博客地址：

源码下载地址：

最近在做各个大公司的笔试题，比如阿里，腾讯，cvte等等，经常会遇到关于快速排序的各种算法题，包括时间复杂度，空间复杂度的分析与计算等等，于是本人查阅了相关的资料，先总结如下

本篇博客主要讲解一下三点

快排是怎样实现的？
怎样用最快的速度找出数组中出现次数超过一半的数字
要求找出数组中最小的第k个数，时间复杂度最低

快排是怎样实现的？

举例说明一下吧，这个可能不是太好理解。假设要排序的序列为?

2 2 4 9 3 6 7 1 5

首先用2当作基准，使用i，j两个指针分别从两边进行扫描，把比2小的元素和比2大的元素分开。
首先比较2和5，5比2大，j左移 2 2 4 9 3 6 7 1 5 比较2和1，1小于2，所以把1放在2的位置，即 2 1 4 9 3 6 7 1 5 ；
接着比较2和4，4大于2，因此将4移动到后面。即2 1 4 9 3 6 7 4 5 比较2和7，2和6，2和3，2和9，全部大于2，满足条件，因此不变
4.经过第一轮的快速排序，元素变为下面的样子

1 2 4 9 3 6 7 5

之后，在把2左边的元素进行快排，由于只有一个元素，因此快排结束。右边进行快排，递归进行，最终生成最后的结果。

下面我们来看一下源码是怎样实现的

简单来说就是先找出一个索引，左边的数都比他小，右边的数都比他大，接着利用递归排列左边和右边的数，知道low>=high

private static void qSort(int[] data, int low, int high) {
    int pivot;
    if (low < high) {
        pivot = partition(data, low, high);
        qSort(data, 0, pivot - 1);
        qSort(data, pivot + 1, high);
    }
}

下面我们来看一下partition函数式怎样实现的

private static int partition(int[] data, int low, int high) {
int pivotKey;
`pivotKey = data[low];`
// 将大于基准点的值得数放到后面
while (low < high) {
while (low < high && data[high] >= pivotKey) {//
`high--;`
}
ArrayUtils.exchangeElements(data, low, high);
// 将小于基准点的值得数放到前面
while (low < high && data[low] <= pivotKey) {
`low++;`
}
ArrayUtils.exchangeElements(data, low, high);
}
// 返回基准点的索引
return low;
}

到此快速排序的分析为止

2）数组中第K个最小的数字

一、问题描述

给定一个数组，数组中的数据无序，在一个数组中找出其第k个最小的数，例如对于数组x，x = {3，2，1，4，5，6}，则其第2个最小的数为2。

二、解题思路

本算法跟快排的思想相似，首先在数组中选取一个数centre作为枢纽，将比centre小的数，放到centre的前面将比centre大的数，放到centre的后面。如果此时centre的位置刚好为k，则centre为第k个最小的数；如果此时centre的位置比k前，则第k个最小数一定在centre后面，递归地在其右边寻找；如果此时centre的位置比k后，则第k个最小数一定在centre后面，递归地在其左边寻找。

三、代码

package com.xujun.quicksort;
?
import java.util.Collections;
?
public class MinIndex {
?
static int[] a = new int[] { 20, 9, 3, 5, 26, 100, 8, -1, 7, 50, -5, 20, -1 };
?
public static void main(String[] args) {
?
System.out.println("before sort");
ArrayUtils.printArray(a);
int k=8;
int pivot = findMinIndexInArray(a, k);
System.out.println("after sort");
ArrayUtils.printArray(a);
System.out.println("数组中最小的第"+k+"个数是 " + a[pivot]);
}
?
private static int findMinIndexInArray(int[] data, int k) {
if (data == null || data.length < k) {
return -1;
}
int start = 0;
int end = data.length - 1;
int pivot = partition(data, start, end);
while (pivot != k - 1) {
?
if (pivot < k - 1) {
`start = pivot +` `1;`
`pivot = partition(data, start, end);`
} else {
`end = pivot -` `1;`
`pivot = partition(data, start, end);`
}
}
?
?
return pivot;
?
}
?
private static int partition(int[] data, int low, int high) {
int pivotKey;
/*
`* pivotKey = data[low];// 选取low作为基准点，pivotKey为基准点的值`
`*/`
?
int middle = low + (high - low) / 2;
if (data[low] > data[high]) {// 较大的数存在high中
ArrayUtils.exchangeElements(data, low, high);
}
if (data[middle] > data[high]) {
ArrayUtils.exchangeElements(data, middle, high);
}
if (data[middle] > data[low]) {
ArrayUtils.exchangeElements(data, middle, low);
}
`pivotKey = data[low];// 选取low作为基准点，pivotKey为基准点的值`
// 将大于基准点的值得数放到后面
while (low < high) {
while (low < high && data[high] >= pivotKey) {//
`high--;`
}
`data[low]` `= data[high];`
// 将小于基准点的值得数放到前面
while (low < high && data[low] <= pivotKey) {
`low++;`
}
`data[high]` `= data[low];`
}
`data[low]` `= pivotKey;`
// 返回基准点的索引
return low;
}
?
}

3）数组中出现次数超过一半的数字

一、问题描述

给定一个数组，找出数组中元素出现次数超过数组长度一半的元素?

如数组：?

4, 3, 2, 1, 1, 1, 1, 1, 1, 0 ?

其中超过一半的元素就是 1

二、解题思路

1）本题同样可以医用快速排序的思想来做，如果一个数字出现次数超过一般，那么排好序的数组的中间数肯定就是出现次数超过一半的数字?

2）考虑异常情况下，出现次数没有超过一半?

遍历数组，检查一下

三、代码

package com.xujun.quicksort;
?
import java.util.Collections;
?
public class MoreThanHalf {
?
static int[] a = new int[] { 20, 9, 3, 5, 10,10,10,10,10 };
?
public static void main(String[] args) {
?
System.out.println("before sort");
ArrayUtils.printArray(a);
int k = 8;
int pivot = findMoreHalfInArray(a);
int target = a[pivot];
boolean checkIsMoreThanHalf = checkIsMoreThanHalf(a, target);
if(checkIsMoreThanHalf){
System.out.println("after sort");
ArrayUtils.printArray(a);
?
System.out.println("超过一般的数是="+target);
}else{
System.out.println("没有超过一般的数字");
}
?
}
?
private static boolean checkIsMoreThanHalf(int[] data, int target) {
int half=data.length/2;
int count=0;
for(int i=0;i<data.length;i++){
if(data[i]==target){
`count++;`
}
}
return count>=half?true:false;
?
}
?
private static int findMoreHalfInArray(int[] data) {
if (data == null || data.length <= 0) {
return -1;
}
int start = 0;
int end = data.length - 1;
int half = data.length / 2;
int pivot = partition(data, start, end);
while (pivot != half - 1) {
?
if (pivot < half - 1) {// 枢轴在一半的左边
`start = pivot +` `1;`
`pivot = partition(data, start, end);`
} else {// 枢轴在一半（中间点）的右边
`end = half -` `1;`
`pivot = partition(data, start, end);`
}
}
?
return pivot;
?
}
?
private static int partition(int[] data, int low, int high) {
int pivotKey;
/*
`* pivotKey = data[low];// 选取low作为基准点，pivotKey为基准点的值`
`*/`
?
int middle = low + (high - low) / 2;
if (data[low] > data[high]) {// 较大的数存在high中
ArrayUtils.exchangeElements(data, low, high);
}
if (data[middle] > data[high]) {
ArrayUtils.exchangeElements(data, middle, high);
}
if (data[middle] > data[low]) {
ArrayUtils.exchangeElements(data, middle, low);
}
`pivotKey = data[low];// 选取low作为基准点，pivotKey为基准点的值`
// 将大于基准点的值得数放到后面
while (low < high) {
while (low < high && data[high] >= pivotKey) {//
`high--;`
}
`data[low]` `= data[high];`
// 将小于基准点的值得数放到前面
while (low < high && data[low] <= pivotKey) {
`low++;`
}
`data[high]` `= data[low];`
}
`data[low]` `= pivotKey;`
// 返回基准点的索引
return low;
}
?
}

关于二分查找的，可以参考我的这篇博客二分查找的相关算法题

关于归并排序的的，可以参考我的这篇博客归并排序递归版和非递归版的实现（java）

关于快速排序的，可以参考我的这篇博客?快速排序的相关算法题（java）

转载请注明原博客地址：

源码下载地址：

本文参与?腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2016年05月03日，如有侵权请联系 cloudcommunity@tencent.com 删除

其他

本文分享自作者个人站点/博客?前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与?腾讯云自媒体同步曝光计划? ，欢迎热爱写作的你一起参与！

其他

登录后参与评论

0 条评论

热度

快速排序的相关算法题（java）

快速排序的相关算法题（java）

快速排序的相关算法题（java）

本篇博客主要讲解一下三点

快排是怎样实现的？

下面我们来看一下源码是怎样实现的

2）数组中第K个最小的数字

一、问题描述

二、解题思路

三、代码

3）数组中出现次数超过一半的数字

一、问题描述

二、解题思路

三、代码

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

快速排序的相关算法题（java）

快速排序的相关算法题（java）

快速排序的相关算法题（java）

本篇博客主要讲解一下三点

快排是怎样实现的？

下面我们来看一下源码是怎样实现的

2）数组中第K个 最小的数字

一、问题描述

二、解题思路

三、代码

3）数组中出现次数超过一半的数字

一、问题描述

二、解题思路

三、代码

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

2）数组中第K个最小的数字