快速排序与寻找第k小的数算法

热心的社会主义接班人

发布于 2018-04-27 14:46:57

6040

发布于 2018-04-27 14:46:57

文章被收录于专栏：cs

慕课网首发了，放在垂直领域吧。简书备份。

出现了一点小问题，就是index，要注意。想法网上一大堆，不多说了。

ubuntu18下输入法有问题，sogou没有安装上，打字好累啊。

package day20180425;

public class SortDem {

    public static void main(String[] args) {
        
         int[] arr={32,68,-98,51,88,1};
         display(arr);
        System.out.println();
        quicksort(arr,0,arr.length-1);
        display(arr);

    }
    
    static int keyfid(int[] arr,int left ,int right)
    {
        int i=left,j=right,temp;
         int p=arr[left];
     /*
      * 是i<j，当二个相遇的时候就要交换   
      * 还可以变成 while(i!=j) 
      */
        while(i<j)
        {
        // 当大于等与关键字就要交换 
           while(i<j&&p<=arr[j])
               j--;
           while(i<j&&p>=arr[i])
               i++;
           if(i<j)
            {
               temp=arr[i];
               arr[i]=arr[j];
               arr[j]=temp;
             }
        }
        
        arr[left]=arr[i];
        arr[i]=p;
        return i;
    }
    
    
    static void quicksort(int[] arr, int left,int right)
    {
        int key;
        if(left>right)
        return;
        else
        {
           key=keyfid(arr,left,right);
           quicksort(arr,left,key-1);
           quicksort(arr,key+1,right);
            
        }
        
    }
    
    
    static void display(int[] arr)
    {
        for(int value:arr)
        System.out.print(" "+value);
    }

}

 32 68 -98 51 88 1
 -98 1 32 51 68 88

寻找一个数组中第k小的数,比如 [32 68 -98 51 88 1]中，选择第3小的数，就是32，一种想法是把数字排序，在去下标，但是可以利用快排。其实只要取得轴值就可以了。

static int sort(int[] arr,int k,int left,int right)
    {
        int index;
        index=keyfid(arr,left,right);
        if(k-1==index)
            return arr[index];
        else if(index>k)
        {
            return sort(arr,k,left,index-1);
        }
        else
            return sort(arr,k,index+1,right);
            
        
    }