八大排序演算法
目錄
一、八大排序演算法
1.氣泡排序
畫圖技術不到位,等找到好的畫圖工具再來補齊後面的圖吧!
//氣泡排序 public static void bubbleSort(int[] arr) { if(arr == null || arr.length < 2) { return;//傳入的陣列為空或者長度小於2直接返回 } for(int i = arr.length - 1; i > 0; i--) { for(int j = 0; j < i; j++) { if(arr[j] > arr[j + 1]) {//兩兩進行比較 swap(arr,j,j + 1);//若前面的數比後面的大,交換這兩個數 } } } } public static void swap(int[] arr, int j, int i) { //int temp = arr[j]; //arr[j] = arr[i]; //arr[i] = temp; arr[i] = arr[i] ^ arr[j]; arr[j] = arr[i] ^ arr[j]; arr[i] = arr[i] ^ arr[j]; }
2.選擇排序
public static void selectSort(int[] arr) { if(arr == null || arr.length < 2) { return; } for(int i = 0; i < arr.length - 1; i++) { int minIndex = i;//先把i指向的位置的數設定為最小下標 for(int j = i + 1; j < arr.length; j++) {//找出這一輪最小值對應的下標 if(arr[j] < arr[minIndex]) {//若存在,值比最小下標小,則更新最小下標 minIndex = j; } } swap(arr,i,minIndex);//使得這一輪的最小值歸位 } }
3.插入排序
public static void insertSort(int[] arr) { if(arr == null || arr.length < 2) { return; } for(int i = 1; i < arr.length; i++) {//將外層迴圈的數插入到前面有序的陣列中 //對前面的陣列進行排序:插入的數 從後往前依次比較, 插入的數小就一直往前交換 for(int j = i - 1; j >=0 && arr[j] > arr[j + 1];j--) { swap(arr,j,j + 1); } } }
4.希爾排序
public static void shellSort(int[] arr) { if(arr == null || arr.length < 2) { return; } int h = 3;//步長定為3 while(h >= 1) { for(int i = h; i < arr.length; i++) { for(int j = i - h; j >= 0 && arr[j] > arr[j + h]; j -= h) { swap(arr,j,j+h); } } h = h/3; } }
5.歸併排序
public static void mergeSort(int[]arr) { if(arr == null || arr.length < 2) { return; } mergeSort(arr,0,arr.length - 1); } public static void mergeSort(int[] arr,int low, int high) { if(low == high) {//遞迴的終點 return; } int mid = low + (high - low)/2; mergeSort(arr, low, mid - 1);//遞迴排序左半部分 mergeSort(arr,mid + 1, high);//遞迴排序右半部分 merge(arr,low,mid,high);//合併 } public static void merge(int[] arr,int low, int mid, int high) { //生成一個輔助陣列,大小和原陣列相同 int[] help = new int[high - low + 1]; int less = arr[low];//less指向左邊陣列第一個數 int more = arr[mid + 1];//more指向右邊陣列第一個數 int i = 0; //輔助陣列help的索引 while(less <= mid && more <= high) { if(arr[less] <= arr[more]){//陣列兩遍哪邊的數小就填進輔助陣列 arr[i++] = arr[less++]; }else { arr[i++] = arr[more++]; } } //處理剩餘部分 //右邊陣列耗盡,把左邊陣列拷貝到輔助陣列 while(less <= mid) { help[i++] = arr[less++]; } //左邊陣列耗盡,把右邊陣列拷貝到輔助陣列 while(more <= mid) { help[i++] = arr[more++]; } //把help陣列拷貝到原陣列中去 for(int j = 0; j < help.length; j++) { arr[low + 1] = help[i]; } }
6.快速排序
public static void quickSort(int[] arr, int low, int high) { if(low <= high) { //產生low-high上的隨機數,把這個索引的看做目標數換到陣列的最後 swap(arr,low + (int)(Math.random()*(high - low + 1)),high); int[] p = patition(arr,low,high);//小於目標數的放左邊,大於放右邊,等於放中間 quickSort(arr, low, p[0] - 1);//遞迴排序小於區域 quickSort(arr, p[1] + 1, high);//遞迴排序大於區域 } } public static int[] patition(int[] arr,int low, int high) { int less = low - 1; //less指向陣列的前一位置 ,low~less為小於區域 int more = high;//more指向最後一個元素,把high元素作為目標數,more - 1~high為大於區域 while(low < more) {//low作為當前數,直到跟大於區域相等 迴圈結束 if(arr[low] < arr[more]) { //當前數比目標數小,跟小於區域的下一個數交換,小於區域的數+1,當前數向後移動 swap(arr, ++less, low++); }else if(arr[low] > arr[more]){ //當前數比目標數大,跟大於區域的前一個數交換,大於區域數+1,當前數不移動 swap(arr, --more, low); }else { //當前數等於目標數,繼續移動 low++; } } swap(arr,more,high); //把目標數歸到等於區域 return new int[] {less + 1,more}; //返回等於區域的左下標和右下標 }
7.堆排序
public static void heapSort(int[] arr) { if (arr == null || arr.length < 2) { return; } //構造堆 //方法一:可以直接從陣列頭開始向堆中新增元素 /*for (int i = 0; i < arr.length; i++) { heapInsert(arr, i); }*/ int size = arr.length; //方法二:直接把陣列看做堆然後從最後一個父節點開始調整 for(int i = (size - 1)/2; i >= 0; i--) { heapify(arr,i,size); } //排序:把堆頂的值和最後一個元素進行交換,並且當前堆長度減少1,然後進行調整使得成為 while (size > 0) { swap(arr, 0, --size); heapify(arr, 0, size); } } //向堆中插入元素/上浮 public static void heapInsert(int[] arr, int index) { //while (arr[index] > arr[(index - 1) / 2]) { //swap(arr, index, (index - 1) / 2); //index = (index - 1) / 2; //} } //堆中的某個元素變化,調整堆結構/ 下沉 public static void heapify(int[] arr, int index, int size) { while (index * 2 + 1 < size) { int left = index * 2 + 1; if(left + 1 < size && arr[left + 1] > arr[left]) { left++; } if(arr[left] <= arr[index]) { break; } swap(arr,index,left); index = left; } }
8.桶排序
public static void bucketSort(int[] arr) { if (arr == null || arr.length < 2) { return; } int max = Integer.MIN_VALUE; // 遍歷找到陣列中的最大值 for (int i = 0; i < arr.length; i++) { max = Math.max(max, arr[i]); } // 建立一個max+1大小的陣列作為桶 int[] bucket = new int[max + 1]; // 遍歷需要排序的陣列,元素的值等於多少就填進那個桶中 for (int i = 0; i < arr.length; i++) { bucket[arr[i]]++; } // 取出桶中的元素恢復到原陣列中 int j = 0;// arr陣列的索引 for (int i = 0; i < bucket.length; i++) { while (bucket[i]-- > 0) { arr[j++] = i; } } }
二、排序演算法複雜度
三、對數器的使用
為了檢測演算法是否正確,自己的用例可能具有隨機性,使用比較器來實現隨機。另外在OJ中也可以自己控制隨機數的範圍。
/** * 設定對數器,用來檢驗結果正確性 */ // 1.先有一個絕對正確的方法, 一般是一個複雜度不高但是正確的方法 public static void comparator(int[] arr) { Arrays.sort(arr); } // 2.實現一個隨機樣本產生器 /** * @param maxSize隨機陣列的最大長度,例如傳入10,產生[0,11)的隨機數,對於int來說就是1-10 * @param maxValue隨機陣列中元素的隨機值的最大值 * @return返回一個隨機長度並且元素也是隨機的一個數組 */ public static int[] generateRandomArray(int maxSize, int maxValue) { int arr[] = new int[(int) ((maxSize + 1) * Math.random())]; for (int i = 0; i < arr.length; i++) { arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) ((maxValue + 1) * Math.random()); } return arr; } //3.實現一個比對方法 public static boolean isEqual(int arr1[],int arr2[]) { if(arr1 == null && arr2 != null || arr1 != null && arr2 ==null) { return false; } if(arr1 == null && arr2 == null) { return true; } if(arr1.length != arr2.length) { return false; } for(int i = 0; i < arr1.length; i++) { if(arr1[i] != arr2[i]) { return false; } } return true; } //比較很多次兩個方法產生的結果 檢視是否相同相同 public static void main(String[] args) { int testTime = 10000; //測試次數 int maxSize = 30;//陣列的最大尺寸 int maxValue = 100;//陣列中元素的最大值 boolean succeed = true; for (int i = 0; i < testTime; i++) { int arr1[] = generateRandomArray(maxSize, maxValue);//產生隨機陣列 int arr2[] = arrayCopy(arr1);//拷貝陣列,讓這兩個陣列結構完全相同 bubbleSort(arr1);//需要測試的方法 comparator(arr2);//絕對正確的方法 if(!isEqual(arr1, arr2)) { succeed = false; break;//判斷出不相同就調出迴圈 } } System.out.println(succeed ? "Succeed!" : "Error!"); int [] arr = generateRandomArray(maxSize, maxValue); System.out.println(Arrays.toString(arr)); bubbleSort(arr); System.out.println(Arrays.toString(arr)); } //拷貝陣列 public static int[] arrayCopy(int[] arr) { if(arr == null) { return null; } int[] res = new int[arr.length]; for (int i = 0; i < arr.length; i++) { res[i] = arr[i]; } return res; }
四、比較器的使用
public class Comparator { //實現Comparator介面,並覆蓋compare方法 public static class IdAscendingComparator implements java.util.Comparator<Student>{ @Override public int compare(Student o1, Student o2) { if(o1.id < o2.id) {//o1小返回負數 return -1; }else if(o1.id > o2.id){//o1大返回正數 return 1; }else { return 0;//相等返回0 } //return o1.id - o2.id;//簡寫 } } public static void main(String[] args) { Student student1 = new Student("A", 1, 23); Student student2 = new Student("B", 2, 21); Student student3 = new Student("C", 3, 22); Student[] students = new Student[] { student3, student2, student1 }; System.out.println(Arrays.toString(students)); Arrays.sort(students, new IdAscendingComparator()); System.out.println(Arrays.toString(students)); } public static class Student { public String name; public int id; public int age; public Student(String name, int id, int age) { this.name = name; this.id = id; this.age = age; } @Override public String toString() { return "Student [name=" + name + ", id=" + id + ", age=" + age + "]"; } } }