版权声明:本文为博主原创文章,未经博主允许不得转载。 https://cloud.tencent.com/developer/article/1341937
关于二分查找的,可以参考我的这篇博客二分查找的相关算法题
关于归并排序的的,可以参考我的这篇博客归并排序 递归版和非递归版的实现(java)
关于快速排序的,可以参考我的这篇博客 快速排序的相关算法题(java)
最近在做各个大公司的笔试题 ,比如阿里,腾讯,cvte等等,经常会遇到关于快速排序的各种算法题,包括时间复杂度,空间复杂度的分析与计算等等,于是本人查阅了相关的资料,先总结如下
举例说明一下吧,这个可能不是太好理解。假设要排序的序列为
2 2 4 9 3 6 7 1 5
1 2 4 9 3 6 7 5
之后,在把2左边的元素进行快排,由于只有一个元素,因此快排结束。右边进行快排,递归进行,最终生成最后的结果。
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);
}
}
private
static
int partition(int[] data,
int low,
int high)
{
int pivotKey;
// 将大于基准点的值得数放到后面
while
(low < high)
{
while
(low < high && data[high]
>= pivotKey)
{//
}
ArrayUtils.exchangeElements(data, low, high);
// 将小于基准点的值得数放到前面
while
(low < high && data[low]
<= pivotKey)
{
}
ArrayUtils.exchangeElements(data, low, high);
}
// 返回基准点的索引
return low;
}
到此快速排序的分析为止
给定一个数组,数组中的数据无序,在一个数组中找出其第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)
{
}
else
{
}
}
return pivot;
}
private
static
int partition(int[] data,
int low,
int high)
{
int 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);
}
// 将大于基准点的值得数放到后面
while
(low < high)
{
while
(low < high && data[high]
>= pivotKey)
{//
}
// 将小于基准点的值得数放到前面
while
(low < high && data[low]
<= pivotKey)
{
}
}
// 返回基准点的索引
return low;
}
}
给定一个数组,找出数组中元素出现次数超过数组长度一半的元素
如数组:
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){
}
}
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)
{// 枢轴在一半的 左边
}
else
{// 枢轴在一半(中间点)的右边
}
}
return pivot;
}
private
static
int partition(int[] data,
int low,
int high)
{
int 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);
}
// 将大于基准点的值得数放到后面
while
(low < high)
{
while
(low < high && data[high]
>= pivotKey)
{//
}
// 将小于基准点的值得数放到前面
while
(low < high && data[low]
<= pivotKey)
{
}
}
// 返回基准点的索引
return low;
}
}
关于二分查找的,可以参考我的这篇博客二分查找的相关算法题
关于归并排序的的,可以参考我的这篇博客归并排序 递归版和非递归版的实现(java)
关于快速排序的,可以参考我的这篇博客 快速排序的相关算法题(java)