Java交換排序：冒泡排序和快速排序

Java交換排序：冒泡排序和快速排序

冒泡排序：

冒泡排序（Bubble Sort）是一種典型的交換排序，比較相鄰的數值大小，若相鄰中兩個數值，前一個數值大于后一個數值，則交換他們兩個的位置；否則，不交換，以此類推，直到最后一個數字， （數值小的往前放，數值大的往后放） 就像石頭沉入水底一樣，小石頭質量小，冒泡小；大石頭質量大，冒泡大，

舉例：有一個原陣列，經歷一次冒泡排序的程序;原陣列為：14,6,3,10,2

 第一次比較：14和6比較，14>6，他們兩個交換位置;

 第二次比較：14和3比較，14>3，他們兩個交換位置;

 第三次比較：14和10比較，14>10，他們兩個交換位置;

 第四次比較：14和2比較，14>2，他們兩個交換位置;

冒泡練習：隨機產生5個1到100的數字，裝入陣列，然后通過冒泡排序，由小到大排列出來

package com.zzm.sort;

import java.util.Random;

public class Bubble {
    public static void main(String[] args) {
        bubble();
    }

    // 冒泡-隨機產生5個1到100的數字
    public static void bubble() {
        int[] arr = new int[5];
        for (int i = 0; i < 5; i++) {
            arr[i] = new Random().nextInt(100) + 1;// 隨機產生5個1到100的數字
        }
        System.out.println("冒泡排序原來陣列：");
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
        System.out.println("-----------------------------------");

        for (int i = 0; i < arr.length - 1; i++) {// 排序次數，數字長度為5，因為只用比較4次，所以減1
            for (int j = 0; j < arr.length - 1 - i; j++) {// 每次排序大的放后面，因為j+1>陣列長度，所以減1；因為每排一輪最大的就放后面了，減i可以增加效率
                if (arr[j] >= arr[j + 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
            System.out.print("第" + (i + 1) + "次排序結果：");
            for (int k = 0; k < arr.length; k++) {
                System.out.print(arr[k] + " ");
            }
            System.out.println();
        }
    }
}

快速排序：

快速排序：快速排序其實是冒泡排序的一種改進版；在冒泡排序中，比較的是相鄰的兩個數，進過比較，大數值的往后面方法，小數值的往前面放，每次遍歷一次陣列，就能找到一個遍歷中最大的數，放在最后，經過多次遍歷陣列，多次找到遍歷中最大的數放在后面，最終實作陣列由小到大排序，而快速排序，是在要排序的原陣列中，找一個數作為標準，與第一個數或者最后一個數作比較，最終實作，這個作為標準的數，它左邊的數都比它小，它右邊的數狗比它大，這就算是完成一次排序了，再經過遞回，就可以實作陣列的由小到大的陣列排序，

舉例：有一個原陣列，經理一次快速排序的程序;原陣列為：58,62,42,92,35

 我選著第一個數58作為標準；大的放后面，小的放前面

第一次比較：58和35比較，58>35,58在前面，35在后面，交換它們的位置

第二次比較：58和62比較，58<62,58在后面，62在前面，交換它們的位置

第三次比較：58和92比較，58<92,58在前面，92在后面，不變換位置

第四次比較：58和42比較，58>42,58在前面，42在后面，交換它們的位置

第一次排序完成后：58左邊的數都比58小，58右邊的數都比58大；

快排練習：隨機產生5個1到100的數字，裝入陣列，然后通過快速排序排序，由小到大排列出來

package com.zzm.sort;

import java.util.Random;

public class Quicksort {
    public static void main(String[] args) {
        int[] arr=new int[5];
        for(int i=0;i<5;i++){
            arr[i]=new Random().nextInt(100)+1;
        }
        System.out.println("原生快速排序陣列為：");
        for(int j=0;j<5;j++){
            System.out.print(arr[j]+" ");
        }
        System.out.println();
        System.out.println("-------------------");
        
        int start=0;
        int end=arr.length-1;
        quicksort(arr,start,end);
        System.out.println("快速排序后的陣列為：");
        for(int k=0;k<5;k++){
            System.out.print(arr[k]+" ");
        }
        
    }

    public static void quicksort(int[] arr, int low ,int high) {
        int start=low;
        int end=high;
        int key=arr[low];//不變的
        
        while(end>start){//快排第一遍，找到一個數左邊的都比他小，右邊的都比他大
            while(end>start&&arr[end]>=key){//拿第一個數跟最后一個數比
                end--;//第一個數比最后一個數小，就比倒數第二個，，，，以此類推
                }
                if(arr[end]<=key){//如果第一個數>=最后一個數，就交換位置
                    int t=arr[end];
                    arr[end]=arr[start];
                    arr[start]=t;
                }
            while(end>start&&arr[start]<=key){
                start++;    
                }
                if(arr[start]>=key){
                    int t=arr[start];
                    arr[start]=arr[end];
                    arr[end]=t;
                }
            }
            
            if(start>low){//標準數，左邊的遞回
                quicksort(arr,low,start-1);
            }
            if(end<high){//標準數，右邊的遞回
                quicksort(arr,end+1,high);
            }
            
        }
        
}
    
    

標籤：其他

上一篇：資料結構（C語言版）---樹

下一篇：簡單DP（動態規劃）