激情久久久_欧美视频区_成人av免费_不卡视频一二三区_欧美精品在欧美一区二区少妇_欧美一区二区三区的

服務器之家:專注于服務器技術及軟件下載分享
分類導航

PHP教程|ASP.NET教程|JAVA教程|ASP教程|編程技術|正則表達式|C/C++|IOS|C#|Swift|Android|JavaScript|易語言|

香港云服务器
服務器之家 - 編程語言 - JAVA教程 - Java編程基于快速排序的三個算法題實例代碼

Java編程基于快速排序的三個算法題實例代碼

2021-03-26 13:33tuke_tuke JAVA教程

這篇文章主要介紹了Java編程基于快速排序的三個算法題實例代碼,小編覺得還是挺不錯的,具有一定借鑒價值,需要的朋友可以參考下

快速排序原理簡介

快速排序是我們之前學習的冒泡排序的升級,他們都屬于交換類排序,都是采用不斷的比較和移動來實現排序的。快速排序是一種非常高效的排序算法,它的實現,增大了記錄的比較和移動的距離,將關鍵字較大的記錄從前面直接移動到后面,關鍵字較小的記錄從后面直接移動到前面,從而減少了總的比較次數和移動次數。同時采用“分而治之”的思想,把大的拆分為小的,小的拆分為更小的,其原理如下:對于給定的一組記錄,選擇一個基準元素,通常選擇第一個元素或者最后一個元素,通過一趟掃描,將待排序列分成兩部分,一部分比基準元素小,一部分大于等于基準元素,此時基準元素在其排好序后的正確位置,然后再用同樣的方法遞歸地排序劃分的兩部分,直到序列中的所有記錄均有序為止。

一,最小的k個數

輸入n個數,找出其中最小的k個數,例如輸入4,5,1,6,2,7,3,8,個數字,則最小的數字是1,2,3,4

基于O(n)的算法,可以用基于Partion函數解決這個問題,如果基于數組的第k個數字來調整,使得比第k個數字小的所有數字都位于數組的左邊,比第k個數組大的所有數字都位于數組的右邊,這樣調整之后數組左邊的k個數字就是最小的k個數字,不一定有序

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner in=new Scanner(System.in);
        int n=in.nextint();
        int k=in.nextint();
        int[] num=new int[n];
        int[] out=new int[k];
        for (int i=0;i<n;i++){
            num[i]=in.nextint();
        }
        Boolean b=GetMinK(n,num,k,out);
        if(b){
            for (int i=0;i<k;i++){
                System.out.print(out[i]+" ");
            }
        }
    }
    public static Boolean GetMinK(int uiInputNum, int[] pInputArray, int uiK, int[] pOutputArray){
        if(pInputArray==null||pOutputArray==null||uiK>uiInputNum||uiInputNum<=0||uiK<=0){
            return false;
        }
        int start=0;
        int end=uiInputNum-1;
        int index=partition(pInputArray,start,end);
        while(index!=uiK-1){
            if(index>uiK-1){
                //index在k-1的右邊
                end=index-1;
                index=partition(pInputArray,start,end);
            } else{
                start=index+1;
                index=partition(pInputArray,start,end);
            }
        }
        for (int i=0;i<uiK;i++){
            pOutputArray[i]=pInputArray[i];
        }
        return true;
    }
    //partion分區函數,返回數組a的首元素快排的索引值index
    public static int partition(int[] a,int start,int end){
        int privot=a[start];
        int i=start;
        int j=end;
        while(i<j){
            while(i<j&&privot<=a[j]){
                j--;
            }
            swap(a,i,j);
            while(i<j&&privot>=a[i]){
                i++;
            }
            swap(a,i,j);
        }
        return i;
    }
    public static void swap(int[] a,int i,int j){
        int t=a[i];
        a[i]=a[j];
        a[j]=t;
    }
}

二,數組中出現次數超過一半的數字

數組中有一個數字出現次數超過數組長度的一半,請找出這個數字。例如1,2,3,2,2,2,5,4,2,數字2在數組中出現了5次,超過數組長度的一半,輸出2

受快速排序的啟發,在快速排序中,現在數組中選擇一個數字,然后調整數組中的數字的順序,使得比選中數字小的數字都排在它的左邊,比選中數字大的數字都排在它的右邊。

如果選中的數字的下標剛好是n/2,那么這個數字就是數組中的中位數

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner in=new Scanner(System.in);
        int n=in.nextint();
        int[] num=new int[n];
        for (int i=0;i<n;i++){
            num[i]=in.nextint();
        }
        int b=GetHalfNum(n,num);
        if(b!=-1){
            System.out.println(b);
        }
    }
    public static int GetHalfNum(int uiInputNum, int[] pInputArray){
        if(pInputArray==null||uiInputNum<=0){
            return -1;
        }
        int middle=uiInputNum>>1;
        //長度的一半
        int start=0;
        int end=uiInputNum-1;
        int index=partition(pInputArray,start,end);
        while(index!=middle){
            //如果不等于長度的一半說明就沒有找到這個中位數
            if(index>middle){
                end=index-1;
                index=partition(pInputArray,start,end);
            } else{
                start=index+1;
                index=partition(pInputArray,start,end);
            }
        }
        return pInputArray[index];
        //index=middle
    }
    public static int partition(int[] a,int start,int end){
        int privot=a[start];
        int i=start;
        int j=end;
        while(i<j){
            while(i<j&&privot<=a[j]){
                j--;
            }
            swap(a,i,j);
            while(i<j&&privot>=a[i]){
                i++;
            }
            swap(a,i,j);
        }
        return i;
    }
    public static void swap(int[] a,int i,int j){
        int t=a[i];
        a[i]=a[j];
        a[j]=t;
    }
}

三,找出數組中第k個最小的數

例如給定數組1,5,2,6,8,0,6中,第4小的數字是5

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner in=new Scanner(System.in);
        int n=in.nextint();
        int k=in.nextint();
        int[] num=new int[n];
        //int[] out=new int[k];
        for (int i=0;i<n;i++){
            num[i]=in.nextint();
        }
        int b=GetMinK(n,num,k);
        if(b!=-1){
            System.out.println(b);
        }
    }
    public static int GetMinK(int uiInputNum, int[] pInputArray, int uiK){
        if(pInputArray==null||uiK>uiInputNum||uiInputNum<=0||uiK<=0){
            return -1;
        }
        int start=0;
        int end=uiInputNum-1;
        int index=partition(pInputArray,start,end);
        while(index!=uiK-1){
            //如果index不是k-1的位置
            if(index>uiK-1){
                end=index-1;
                index=partition(pInputArray,start,end);
            } else{
                start=index+1;
                index=partition(pInputArray,start,end);
            }
        }
        return pInputArray[index];
        //返回的這個位置的數值
    }
    public static int partition(int[] a,int start,int end){
        int privot=a[start];
        int i=start;
        int j=end;
        while(i<j){
            while(i<j&&privot<=a[j]){
                j--;
            }
            swap(a,i,j);
            while(i<j&&privot>=a[i]){
                i++;
            }
            swap(a,i,j);
        }
        return i;
    }
    public static void swap(int[] a,int i,int j){
        int t=a[i];
        a[i]=a[j];
        a[j]=t;
    }
}

總結

以上就是本文關于Java編程基于快速排序的三個算法題實例代碼的全部內容,希望對大家有所幫助。感興趣的朋友可以繼續參閱本站其他相關專題,如有不足之處,歡迎留言指出。感謝朋友們對本站的支持!

原文鏈接:http://blog.csdn.net/tuke_tuke/article/details/51476630

延伸 · 閱讀

精彩推薦
531
主站蜘蛛池模板: 久久久久久久久国产 | 毛片在线免费观看完整版 | 中国洗澡偷拍在线播放 | 久久亚洲精品国产 | 午夜国产在线观看 | 久久免费视频精品 | 中国美女一级黄色大片 | 久久亚洲精品国产一区 | 91色爱 | 日韩视| 国产成年人视频网站 | 久久成人免费观看 | 日韩视频―中文字幕 | 911视频免费版 | 国产成人精品一区二区仙踪林 | 精品一区二区三区免费毛片爱 | 久草网在线| 久久久久久久一区二区三区 | 亚洲最大的成人网 | 久久久久久久一区 | 亚洲精品午夜视频 | 久久精品国产久精国产 | 黄色av网站免费 | 香蕉视频破解 | 黄色免费大片 | 夜夜看 | 久久蜜桃精品一区二区三区综合网 | 国产一区精品视频 | 又黄又爽免费无遮挡在线观看 | 国产毛片自拍 | 国产精品免费一区二区三区四区 | 91av大片| 国产精品视频中文字幕 | 91重口视频 | 欧美又黄又嫩大片a级 | 国产九色在线播放九色 | 欧美黑人一级 | 日韩视频一| 国产精品久久久久久久不卡 | 91精品国产综合久久久欧美 | 国产一区二区三区四区五区加勒比 |