數組排序:快速排序,選擇排序,冒泡排序,插入排序

一下介紹四種數組的常用排序方式

快速排序:時間複雜度最低,效率最高

package shuzu;

import java.util.Arrays;

import java.util.Random;

public class ArraySortsizhong {

public static void main(String[] args) {

int[] a=new int[10];//初始化裡面所有元素為0

int[] b={1,2,3,4,5};//隻能在聲明時使用!

int[] c=new int[]{7,2,3,4,9,15,17};//可以在非聲明時使用

/*
     for循環的兩種 idea快捷鍵itar iter(增強for循環)
      */
           

// //增強的for循環foreach,快捷鍵iter

// for (int i:b) {

// System.out.println(i);

// //foreach隻能讀不能寫

// }

Random random=new Random();

Random傳入的種子相同得到的随機數一樣

// System.out.println(random.nextInt(100));

// //生成的數字包括0不包括100

// System.out.println(random.nextInt(100));

// System.out.println(random.nextInt(100));

for (int i = 0; i < a.length; i++) {
        a[i]=random.nextInt(50);
    }

     System.out.println("數組最初的狀态為:"+Arrays.toString(a));


    //排序算法:插入選擇,快速,冒泡,選擇

    //selectSort(a);
    //insertSort(a);
    //bubbleSort(a);
    quickSort(a);


    for (int i:a) {
        System.out.println(i);
    }
}

public static void selectSort(int[] a){
    //選擇排序:每次選擇出最小的數放在目前循環的開始下标處
    for (int i = 0; i < a.length; i++) {
        int min=i;
        for (int j = i+1; j < a.length; j++) {
            if(a[min]>a[j]){
                min=j;
            }
        }
        if (min!=i){
            change(a,i,min);
        }
        System.out.println(Arrays.toString(a));
    }
}

public static void insertSort(int[] a){
    //插入排序:假設前面的數字已經完成排序,當一個新數加入時,從後往前判斷大小,直到冒泡把要插入的數字放入合适的位置-
    for (int i = 1; i < a.length; i++) {
        for (int j = i; j > 0; j--) {
            if(a[j-1]>a[j]){
                change(a,j-1,j);
            }else {
                break;
            }
        }
        System.out.println(Arrays.toString(a));
    }
}

public static void bubbleSort(int[] a){
    //冒泡排序,第一遍通過兩兩的比較将最大的值下沉的最後一位,第二遍沉第二大的到倒數第二位....


    for (int i = 0; i < a.length; i++) {
        for (int j = 0; j < a.length-i-1; j++) {
            if (a[j]>a[j+1]){
                change(a,j,j+1);
            }
        }
        System.out.println(Arrays.toString(a));
    }
}

//快速排序:在數組中選取一個中間值,将他和最後一位的數字交換,定義一個index記錄數組中有幾個比[end](所選中的值)小的
//周遊整個數組,将index指向[0],将a[i]和a[end]進行比較,如果a[i]小于a[end],将a[i]和a[index]進行交換(把比标杆值小的數放在前面),并且把index++指向下一個位置
//最後将a[end]和a[index]交換,将比标杆大的數和比标杆小的數分成兩堆,至于标杆的兩側
//最後遞歸調用該方法即可,遞歸的出口就是start>=end


public static  void quickSort(int[] a){
      quickSort(a,0,a.length-1);
}
public static void quickSort(int[] a,int start,int end){
    if (start >= end) {
        return;
    }
    Random random=new Random();
    int index = random.nextInt(end - start + 1) + start;
    change(a, index, end);
    index = start;
    for (int i = start; i < end; i++) {
        if (a[i] < a[end]) {
            change(a, index, i);
            index++;
        }
    }
    change(a,index,end);
    quickSort(a,start,index-1);
    quickSort(a,index+1,end);
}

public static void change(int[] a,int i,int j){
           

// a[i] ^=a[j];

// a[j] ^=a[i];

// a[i] ^=a[j];

int temp;

temp=a[i];

a[i]=a[j];

a[j]=temp;

}

}