1冒泡排序

比較相鄰的元素，將小的放到前面,(每一輪找出數組中最大的放在后面，后面排好序的數組元素不參與下輪排序)。 下面將數組[7,8,5,1,3]里面的元素進行排序。 7 8 5 1 3

1.1:? ?7 8 5 1 3? ? ?7和8進行比較，因為7<8所以2個元素的位置不變
1.2:? ?5 7 1 3 8? ? ?8和5進行比較，因為8>5所以2個元素的位置互換
1.3:? ?7 5 1 8 3? ? ?8和1進行比較，因為8>1所以2個元素的位置互換
1.4:? ?7 5 1 3 8? ? ?同理，8和3互換位置，得到最大數8，并且不參與下一輪排序
2.1:? ?5 7 1 3 8? ? ?同理第二輪排序得到最大數是7，放在最后，依次得到每一輪的最大值，這樣小的數就在前面，大
的數放在后面，最后得到所要的數組[1,3,5,7,8]。

/*** @Description 比較相鄰的元素，將小的放到前面,(每一輪找出數* 組中最大的放在后面，后面排好序的數組元素不參與下輪排序)* @MethodName bubbingSort * @Date 14:51 2019/5/27* @Param [arr]* @Return void* @Throws*/public static void bubbingSort(int[] arr) {//外層循環控制排序趟數for (int i = 0; i < arr.length - 1; i++) {for (int j = 0; j < arr.length - 1 - i; j++) {//內層循環控制每一趟排序多少次if (arr[j] < arr[j + 1]) {int temp = arr[j + 1];arr[j + 1] = arr[j];arr[j] = temp;}System.out.println("bubbingSort " + i + Arrays.toString(arr));}}}

?

2選擇排序

1.將數組中每個元素與第一個元素比較，如果這個元素小于第一個元素，則交換這兩個元素 2.循環第1條規則，找出最小元素，放于第1個位置 3.經過n-1輪比較完成排序 /*** @Description 1.將數組中每個元素與第一個元素比較，如果這個元素小* 于第一個元素，則交換這兩個元素* 2.循環第1條規則，找出最小元素，放于第1個位置* 3.經過n-1輪比較完成排序* @MethodName selectSort* @Date 14:48 2019/5/27* @Param [arr]* @Return void* @Throws*/public static void selectSort(int[] arr) {for (int i = 0; i < arr.length; i++) {int value = arr[i];int position = i;//內層循環查找最小數，并記錄最小數的位置for (int j = i + 1; j < arr.length; j++) {//獲取到最小數之后每次都用最小數于之后的數進行比較if (arr[j] < value) {value = arr[j];position = j;}}//內層循環結束交換arr[position] = arr[i];arr[i] = value;System.out.println("selectSort " + i + Arrays.toString(arr));}}

?

3插入排序

1.將數組分為兩部分, 將后部分的第一個逐一與前部分每一個元素比較，在合理位置插入 2.插入排序算法效率要高于選擇排序和冒泡排序? 7 8 5 1 3 將數組分為7和8,5,1,3兩部分 1: 7? ?8 5 1 3 8>7，所以位置不變 2: 5? ?7 8 1 3 5<8 && 5<7,所以5放到7和8的前面? 3: 1? ?5 7 8 3 1< 8 && 1<7 && 1<5,所以1放到5,7,8的前面 4: 1? ?3 5 7 8 將3依次和前面元素比較，得到3<5,1>3，所以3在1和5之間，結束? /*** @Description 1.將數組分為兩部分, 將后部分的第一個逐一與前部分每* 一個元素比較，在合理位置插入 Arrays.sort(); 快排* 2.插入排序算法效率要高于選擇排序和冒泡排序* @MethodName insertSort* @Date 14:54 2019/5/27* @Param [arr]* @Return void* @Throws*/public static void insertSort(int[] arr) {int insertNum;for (int i = 1; i < arr.length; i++) {//從第一個數開始執行插入insertNum = arr[i];int j = i - 1;//將大于insertNum 向后移動（等于交換位置）while (j >= 0 && arr[j] > insertNum) {arr[j + 1] = arr[j];j--;}arr[j + 1] = insertNum;System.out.println("insertSort " + i + Arrays.toString(arr));}}

4快速排序

通過一趟排序將要排序的數據分割成獨立的兩部分，其中一部分的所有數據都比另外一部分的所有數據都要小，然后再按此方法對這兩部分數據分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數據變成有序序列。 10 4 7 8 5 9 3 12 11 1: 選10位一個基準數，進行第一次排序，小于10的放左邊，大于10的放右邊，得到新的數組[4,7,8,5,9,3,10,12,11],以10為基準分成左右2部分,[4,7,8,5,9, 3],10,[12,11]，兩邊數組分別進行快速排序,以數組第一個元素作為基準進行排序。 當前數據為[4,7,8,5,9,3],10,[12,11] 2: [4,7,8,5,9,3]以第一個元素4作為基準排序得到[3,4,5,7,8,9]；后面的數組為[11,12]，結束。 當前數據為[3],4,[5,7,8,9],10,11,12，因為3為單個的，所以[3]不需再進行排序，目前只需對[5,7,8,9]進行處理 3: [5,7,8,9],以第一個元素5作為基準排序，得到5,[,7,8,9]當前數據為3,4,5,[7,8,9],10,11,12 4: 類似步驟3，分別把7,8,9給獨立出來，最終得到數據3,4,5,7,8,9,10,11,12 /*** @Description 選擇一個基數，小于基數的在左邊，大于基數在右邊 通過一趟排序將要排序的數據分割成獨立的兩部分，其中* 一部分的所有數據都比另外一部分的所有數據都要小，然后再按* 此方法對這兩部分數據分別進行快速排序，整個排序過程可以遞* 歸進行，以此達到整個數據變成有序序列* @MethodName quickSort* @Date 16:10 2019/5/27* @Param [a]* @Return void* @Throws*/public static void quickSort(int[] arr, int low, int high) {int i, j, temp, t;if (low > high) {return;}i = low;j = high;//temp就是基準位temp = arr[low];while (i < j) {//先看右邊，依次往左遞減//{5, 2, 7, 3, 8};//5<8 y-1 5《3 不成立 y=3（從右開始找比基數小的位置）while (temp <= arr[j] && i < j) {j--;}//再看左邊，依次往右遞增//{5, 2, 7, 3, 8}; 5>2 i++ i=2 5>7 i=2(從左開始找比基數大的位置）while (temp >= arr[i] && i < j) {i++;}//如果滿足條件則交換 if (i < j) {t = arr[j];arr[j] = arr[i];arr[i] = t;}}//最后將基準為與i和j相等位置的數字交換arr[low] = arr[i];arr[i] = temp;System.out.println("quickSort " + Arrays.toString(arr));//遞歸調用左半數組quickSort(arr, low, j - 1);//遞歸調用右半數組quickSort(arr, j + 1, high);}

?

5歸并排序

該算法是采用分治法（DIVIDE AND CONQUER）的一個非常典型的應用，且各層分治遞歸可以同時進行 /*** @Description 分而治之(divide - conquer);每個遞歸過程涉及三個步驟* 第一, 分解: 把待排序的 n 個元素的序列分解成兩個子序列, 每個子序列包括 n/2 個元素.* 第二, 治理: 對每個子序列分別調用歸并排序MergeSort, 進行遞歸操作* 第三, 合并: 合并兩個排好序的子序列,生成排序結果.* @MethodName mergeSort* @Date 17:23 2019/5/27* @Param [a, low, high]* @Return int[]* @Throws*/public static int[] mergeSort(int[] a, int low, int high) {int mid = (low + high) / 2;if (low < high) {mergeSort(a, low, mid);mergeSort(a, mid + 1, high);//左右歸并 merge(a, low, mid, high);}return a;}public static void merge(int[] a, int low, int mid, int high) {int[] temp = new int[high - low + 1];int i = low;int j = mid + 1;int k = 0;// 把較小的數先移到新數組中while (i <= mid && j <= high) {if (a[i] < a[j]) {temp[k++] = a[i++];} else {temp[k++] = a[j++];}}// 把左邊剩余的數移入數組while (i <= mid) {temp[k++] = a[i++];}// 把右邊邊剩余的數移入數組while (j <= high) {temp[k++] = a[j++];}// 把新數組中的數覆蓋nums數組for (int x = 0; x < temp.length; x++) {a[x + low] = temp[x];}}

?

?

轉載于:https://www.cnblogs.com/fanBlog/p/10932117.html

總結

以上是生活随笔為你收集整理的5中排序算法（冒泡，选择，插入，快速，归并）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。