Java學(xué)習(xí)-----冒泡、選擇、插入、快速排序算法

一.冒泡排序 基本思想：兩個數(shù)比較大小，較大的下沉，小的上浮。 1.第一趟，相鄰的兩個數(shù)比較，后一個數(shù)小，就交換兩數(shù)的位置； 2.依次往后走，最后找到最大的數(shù)； 3.針對所有的數(shù)重復(fù)以上的步驟，除了最后一個； 4.持續(xù)每次對越來越少的數(shù)重復(fù)上面的步驟，直到?jīng)]有任何一對數(shù)字需要比較。

例如： 3，2，7，1，5
第一趟第一次：2，3，7，1，5
第二次：2，3，7，1，5
第三次：2，3，1，7，5
第四次：2，3，1，5，7
第二趟第一次：2，3，1，7，5
第二次：2，1，3，7，5
……
最后：1，2，3，5，7

private static void BubbleSort(int[] arr) { for (int i = 0; i < arr.length; i++) { //表示趟數(shù)，一共走n-1次 for (int j = 0; j < arr.length-1; j++) { if (arr[j] > arr[j + 1]) { int temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; } System.out.print(arr[j]+" "); } System.out.println(); } } 二.選擇排序 基本思想：

在長度為N的無序數(shù)組中，第一次遍歷n-1個數(shù)，找到最小的數(shù)值與第一個元素交換；
第二次遍歷n-2個數(shù)，找到最小的數(shù)值與第二個元素交換；
……
第n-1次遍歷，找到最小的數(shù)值與第n-1個元素交換，排序完成。

private static void SelectionSort(int[] arr){ for(int i=0;iarr[j]){ minIndex=j; } if(minIndex!=i){ int temp = arr[i]; arr[i]=arr[minIndex]; arr[minIndex]=temp; } } } } 三.插入排序 基本思想：

在要排序的一組數(shù)據(jù)中，假定前n-1個數(shù)據(jù)已經(jīng)排好序，將第n個數(shù)據(jù)插入排好序的這個有序數(shù)列中，使得插入后的數(shù)列也是排好序的。如此，反復(fù)循環(huán)，知道全部排好序。

private static void InsertSort(int[] arr) { for (int i = 0; i < arr.length-1; i++) { for (int j = i + 1; j >0; j--) { if (arr[j] < arr[j - 1]) { int temp = arr[j]; arr[j] = arr[j - 1]; arr[j - 1] = temp; } } } } 四.快速排序 基本思想：

通過一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小，然后再按此方法對這兩部分數(shù)據(jù)分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數(shù)據(jù)變成有序序列。

實現(xiàn)思路：

—1.以第一個數(shù)作為基準，將數(shù)組分為兩個子區(qū)，左區(qū)的全部小于等于這個基準值，右區(qū)的大于等于這個基準值。此時，兩個子區(qū)還處于亂序狀態(tài)。
—2.在把左區(qū)作為一個整體，用步驟1再處理一次；右區(qū)同理。
— 3.重復(fù)步驟1.2.直至左區(qū)處理完畢。

private static void QuickSort(int[] arr, int low, int high) { if (low > high) { return; } int key = arr[low]; int i = low; int j = high; while (j > i) { // 從后往前比較 while (j > i && arr[j] >= key) { // 先看右邊，找比基準值小的，依次遞減 j--; } while (j > i && arr[i] < key) { // 再看左邊，找比基準值大的，依次遞增 i++; } if (j > i) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } } // 將i=j的值設(shè)為基準值 arr[low] = arr[i]; arr[i] = key; // 遞歸調(diào)用左區(qū) QuickSort(arr, low, j - 1); // 遞歸調(diào)用右區(qū) QuickSort(arr, j + 1, high); }