1沐序、快排
public void QuickSeach(int[] array,int left,int right){
//快速排序
if(left >right){
return ;
}
int i= left;
int j = right;
int tar = array[left];
// System.out.println("tar:"+tar);
while(i != j){
//先從右往左找到第一個(gè)小于tar值的下標(biāo)
while(array[j] > tar && j>i){
j--;
}
//System.out.println("j:"+array[j]);
//從左往右找到第一個(gè)大于tar值的下標(biāo)
while(array[i] <= tar && i<j){
i++;
}
// System.out.println("i:"+array[i]);
//這兩個(gè)都找到之后，交換i,j所指向的位置
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
//交換此時(shí)循環(huán)退出位置和tar值的
array[left] = array[i];
array[i] = tar;
/*
System.out.println("quickSearch：");
for(int j1 =0;j1<array.length;j1++){
System.out.print(array[j1]+" ");
}
System.out.println();
*/
//然后在快排當(dāng)前位置左邊伪很，和右邊
new Solution().QuickSeach(array, left, i-1);
new Solution().QuickSeach(array,i+1,right);
}
2、數(shù)組中出現(xiàn)次數(shù)超過一半的數(shù)字
public int Partition(int[] array,int left,int right){
//快排的一次實(shí)現(xiàn)
int i = left;
int j = right;
// if(i>j){
// return -1;
// }
int tar = array[left];
while(i!=j){
while(array[j] > tar && j>i){
j--;
}
while(array[i] <= tar && i<j){
i++;
}
//交換
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
//再次交換
array[left] = array[i];
array[i] = tar;
//返回此時(shí)的index
System.out.println("Partition return:"+i);
return i;
}
3、import java.util.ArrayList;
public class Solution {
public int Partition(int[] array,int left,int right){
//快排的一次實(shí)現(xiàn)
int i = left;
int j = right;
// if(i>j){
// return -1;
// }
int tar = array[left];
while(i!=j){
while(array[j] > tar && j>i){
j--;
}
while(array[i] <= tar && i<j){
i++;
}
//交換
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
//再次交換
array[left] = array[i];
array[i] = tar;
//返回此時(shí)的index
System.out.println("Partition return:"+i);
return i;
}
public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
/*
* 輸入n個(gè)整數(shù)景东，找出其中最小的K個(gè)數(shù)。
* 例如輸入4,5,1,6,2,7,3,8這8個(gè)數(shù)字奔誓，則最小的4個(gè)數(shù)字是1,2,3,4,
*思路：使用快排的思想斤吐，如果找到的數(shù)字是位于第k位，那么存到相應(yīng)的數(shù)組中
*
* */
ArrayList<Integer> res = new ArrayList<Integer>();
//先判斷輸入是否合法
if(k>input.length|| k<=0){
return res;
}
int start = 0;
int end = input.length-1;
int index = Partition(input,start,end);
System.out.println("index:"+index);
for(int i =0;i<input.length;i++){
System.out.print(input[i]+" ");
}
System.out.println();;
while(index != k-1){
if(index > k-1){
//遍歷左邊
end = index-1;
index = Partition(input,start,end);
}else{
//遍歷右邊
start = index+1;
index = Partition(input,start,end);
}
}
for(int i =0 ;i<k;i++){
res.add(input[i]);
}
System.out.println("result:");
for(int i=0;i<res.size();i++){
System.out.print(res.get(i)+" ");
}
System.out.println();
return res;
}
}
