快排及其相关题目

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){
        //先从右往左找到第一个小于tar值的下标
        while(array[j] > tar && j>i){
            j--;
        }
        //System.out.println("j:"+array[j]);
        //从左往右找到第一个大于tar值的下标
        while(array[i] <= tar && i<j){
            i++;
        }
    //  System.out.println("i:"+array[i]);
        //这两个都找到之后，交换i,j所指向的位置
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
    //交换此时循环退出位置和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();
    */
    //然后在快排当前位置左边，和右边
    new Solution().QuickSeach(array, left, i-1);
    new Solution().QuickSeach(array,i+1,right);
}

2、数组中出现次数超过一半的数字
public int Partition(int[] array,int left,int right){
//快排的一次实现
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;
//返回此时的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){
//快排的一次实现
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;
//返回此时的index
System.out.println("Partition return:"+i);
return i;
}
public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
/*
* 输入n个整数，找出其中最小的K个数。
* 例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4,
*思路：使用快排的思想，如果找到的数字是位于第k位，那么存到相应的数组中
*
* */

    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;
    
    }

}