文章目錄

• • 冒泡排序
  • 選擇排序
  • 插入排序
  • 希爾排序
  • 堆排序
  • 大頂堆
  • 基數(shù)排序
  • 歸并排序
  • 快速排序

冒泡排序

思想
比較兩個相鄰元素，如果順序錯誤則交換過來
總共比較數(shù)組長度減一次，每次比較 將 那次比較的最大值放到符合的位置
優(yōu)化: 當(dāng)有一次比較，數(shù)組中沒有數(shù)字交換，則證明數(shù)組已經(jīng)是有序的了
圖解

代碼

import java.util.Arrays; //冒泡排序 public class BubbleSort {public static void main(String[] args) {//長度是5 0 1 2 3 4 int arr[] ={3, 9, -1, 10, -2};boolean flag = false;for(int i=0;i<arr.length-1;i++){for(int j=0;j<arr.length-i-1;j++){if(arr[j] > arr[j+1]){flag = true;int temp = arr[j];arr[j] = arr[j+1];arr[j+1] = temp;}}System.out.println(Arrays.toString(arr));//在一趟排序沒有發(fā)生交換則證明已經(jīng)是有序的了if(flag){flag = false;}else{break;}}} }

選擇排序

思想
總共比較數(shù)組長度減一次
在每次比較中記錄最大的數(shù)字的位置
將每次比較出來的最大數(shù)字所在位置和符合的位置進(jìn)行交換
圖解

代碼

import java.util.Arrays; //選擇排序 public class SelectSort {public static void main(String[] args) {int[] arr={101, 34, 119, 1};for(int i=0;i<arr.length-1;i++){int min=i;for(int j=i;j<arr.length;j++){if(arr[min]> arr[j]){min=j;}}//最小值不在最小位置才交換if(min!=i){int temp=arr[i];arr[i]=arr[min];arr[min]=temp;}System.out.println(Arrays.toString(arr));}} }

插入排序

思想
好比整理撲克牌的順序，
將要插入的牌拿出來和前一張牌比較，如果前一張牌比這張牌大 前一張牌后移， 要插入的牌再和前第二張牌比較，如果前第二張牌比這張牌大 前第二張牌后移
以此類推，直到找到符合的位置將這張牌插入
缺點
數(shù)組 arr = {2,3,4,5,6,1} 這時需要插入的數(shù) 1(最小), 這樣的過程是：
{2,3,4,5,6,6}
{2,3,4,5,5,6}
{2,3,4,4,5,6}
{2,3,3,4,5,6}
{2,2,3,4,5,6}
{1,2,3,4,5,6}
結(jié)論: 當(dāng)需要插入的數(shù)是較小的數(shù)時，后移的次數(shù)明顯增多，對效率有影響.
圖解

代碼

public class InsertSort {public static void main(String[] args) {int[] arr={101, 34, 119, 1};for(int i=1;i<arr.length;i++){//存儲要插入牌的位置int index=i;//存儲要插入牌的值int tempValue=arr[i];//每次是和要插入牌的值比較while(index >0 && tempValue < arr[index-1]){arr[index]=arr[index-1];index--;}if(index !=i){arr[index]=tempValue;}System.out.println(Arrays.toString(arr));}} }

希爾排序

思想
希爾排序是 快速排序 基于 分治思想 的改進(jìn)
將數(shù)組分成 數(shù)組長度除二個組(gap) 每個組進(jìn)行插入排序
----只要時大于等于gap的數(shù)字都要要和前面進(jìn)行比較排序
再將數(shù)組分成 gap/2 個數(shù)組進(jìn)行插入排序
當(dāng)gap為1時進(jìn)行最后一次插入排序，即可獲得有序序列
圖解

代碼

public class ShellSort2 {public static void main(String[] args) {int[] arr={8,9,1,7,2,3,5,4,6,0};for(int gap=arr.length/2;gap>0;gap=gap/2){for(int j=gap;j<arr.length;j++){int temp=arr[j];int index=j;while(index-gap>=0 && temp<arr[index-gap]){arr[index]=arr[index-gap];index=index-gap;}if(index != j){arr[index]=temp;}}System.out.println(Arrays.toString(arr));}} }

堆排序

思想
1.將待排序序列構(gòu)造成一個大頂堆
----1.1 找到完全樹的最后一個葉子節(jié)點(有子節(jié)點的節(jié)點)位置為數(shù)組長度/2-1
----1.2 從數(shù)組長度/2-1向前依次進(jìn)行排序
2.此時，整個序列的最大值就是堆頂?shù)母?jié)點。
3.將其與末尾元素進(jìn)行交換，此時末尾就為最大值。
4.然后將剩余n-1個元素重新構(gòu)造成一個堆，這樣會得到n個元素的次小值。
5.如此反復(fù)執(zhí)行，便能得到一個有序序列了。
大頂堆是升序排列，小頂堆是降序排列
圖解
滿二叉樹:
一個二叉樹，如果每一個層的結(jié)點數(shù)都達(dá)到最大值，則這個二叉樹就是滿二叉樹。也就是說，如果一個二叉樹的層數(shù)為K，且結(jié)點總數(shù)是(2^k) -1 ，則它就是滿二叉樹
如下圖: 2^3 -1=7 個節(jié)點

完全二叉樹:
若設(shè)二叉樹的深度為h，除第 h 層外，其它各層 (1～h-1) 的結(jié)點數(shù)都達(dá)到最大個數(shù)，第 h 層所有的結(jié)點都連續(xù)集中在最左邊，這就是完全二叉樹

大頂堆

大頂堆:是完全二叉樹，每個節(jié)點的值大于或等于它的左子節(jié)點和右子節(jié)點的值，沒有要求結(jié)點的左子節(jié)點的值和右子節(jié)點的值的大小關(guān)系。

我們對堆中的結(jié)點按層進(jìn)行編號，映射到數(shù)組中就是下面這個樣子:

大頂堆特點：
arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2] // i 對應(yīng)第幾個節(jié)點，i從0開始編號
小頂堆
小頂堆:是完全二叉樹，每個節(jié)點的值小于或等于它的左子節(jié)點和右子節(jié)點的值，沒有要求結(jié)點的左子節(jié)點的值和右子節(jié)點的值的大小關(guān)系。

代碼

public class HeapSort2 {public static void main(String[] args) {int[] arr={4,6,8,5,9};//1.將數(shù)組調(diào)整成大頂堆//最后一個非葉子節(jié)點為 arr[arr.length/2-1]for(int i=arr.length/2-1;i>=0;i--){//將第i個非葉子節(jié)點,和子節(jié)點比較然后交換位置maxHeapSort(arr,i,arr.length);}System.out.println(Arrays.toString(arr));//每次將大頂堆的根節(jié)點和排序的最后一位交換for(int i=0;i<arr.length;i++){maxHeapSort(arr,0,arr.length-i);int temp=arr[0];arr[0]=arr[arr.length-i-1];arr[arr.length-i-1]=temp;System.out.println(Arrays.toString(arr));}}/*** * @param arr 要排序的數(shù)組* @param i 每次要排序的節(jié)點* @param length 因堆排序要每次得出最大值和排序的最后位替換,這里不用arr.length,因為長度會變化*/private static void maxHeapSort(int[] arr, int i, int length) {//保存此節(jié)點的值int temp=arr[i];//arr[2*i+1]為arr[i]的左節(jié)點for(int k=2*i+1;k<length;k=2*k+1){//判斷右子節(jié)點是否存在,指針指向左右子節(jié)點中的最大值if(k+1<length && arr[k+1]>arr[k]){k++;}//判斷此節(jié)點的值是否 小于 子節(jié)點中的最大值if(temp < arr[k]){//此節(jié)點等于子節(jié)點的值arr[i]=arr[k];//將此節(jié)點坐標(biāo) 變成 子節(jié)的坐標(biāo),用于和下次和子節(jié)點的子節(jié)點比較i=k;}else{break;}//當(dāng)for 循環(huán)結(jié)束后，我們已經(jīng)將以i 為父結(jié)點的樹的最大值，放在了 最頂arr[k]=temp;}} }

基數(shù)排序

思想
----計數(shù)排序：每個桶只存儲單一鍵值；
----桶排序：每個桶存儲一定范圍的數(shù)值；
----基數(shù)排序：根據(jù)鍵值的每位數(shù)字來分配桶；
1、創(chuàng)建桶
----1.1如果排序是數(shù)字則創(chuàng)建10個桶，每個桶最大容量為序列長度
----1.2如果排序的是字母創(chuàng)建26個桶，每個桶最大容量為序列長度
----1.3創(chuàng)建一個數(shù)組用來標(biāo)記每個桶中有多少個元素
2、將序列按要求放到桶中
----2.2 遍歷序列中每個元素，獲得指定位上的值
----2.3 根據(jù)獲得指定位上的值將元素放到指定桶中，標(biāo)記桶中元素個數(shù)的值增加
3、從桶中取出
----3.3按順序遍歷桶中的值，同時將值賦值給原數(shù)組
4、循環(huán)2和3最后得出有序序列
注意: 基數(shù)排序是經(jīng)典的空間換時間的方式，占用內(nèi)存很大, 當(dāng)對海量數(shù)據(jù)排序時，容易造成 OutOfMemoryError
圖解

代碼

public class RadixSort2 {public static void main(String[] args) {int[]arr = {73, 22, 93, 43, 55, 14, 28, 65, 39, 81, 33, 100};sort(arr,3);System.out.println(Arrays.toString(arr));}/*** @param arr 原數(shù)組 * @param i 原數(shù)組 最大數(shù)有幾位數(shù)*/private static void sort(int[] arr, int length) {//創(chuàng)建10個一維數(shù)組,每個數(shù)組中最大有arr.length個數(shù)int[][] tempArr=new int[10][arr.length];//用來標(biāo)記每個一維數(shù)組中有幾個數(shù)int[] indexArr=new int[10];//循環(huán)遍歷某一位for(int i=0,n=1;i<length;i++,n=n*10){//遍歷數(shù)組中每個元素值放到指定桶中for(int j=0;j<arr.length;j++){//得到數(shù)組中每個元素對應(yīng)的桶/*** 個位 /1 %10* 十位 /10 %10* 百位 /100 %10*/int val=arr[j]/n%10;//將元素放到指定桶,同時標(biāo)記這個桶中的元素個數(shù)增加tempArr[val][indexArr[val]++]=arr[j];}int index=0;//將桶中數(shù)據(jù)放到原數(shù)組中for(int k=0;k<10;k++){for(int l=0;l<indexArr[k];l++){arr[index]=tempArr[k][l];index++;}}indexArr=new int[10];}} }

歸并排序

思想
采用分治思想，將數(shù)組拆分成每一個元素，然后合并時進(jìn)行排序
圖解
拆分

合并
綠色數(shù)組 和 紅色數(shù)組 合并為一個 藍(lán)色數(shù)組（temp數(shù)組）
藍(lán)色和紅色數(shù)組各有一個指針，通過比較指針后移按大小順序取出放入temp數(shù)組中

代碼

public class MergeSort {public static void main(String[] args) {int[] arr={9,8,7,6,5,4,3,2,1}; //創(chuàng)建緩存數(shù)組int[] temp=new int[arr.length];//調(diào)用歸并排序merge(arr,0,arr.length-1,temp);System.out.println(Arrays.toString(arr));}/*** 進(jìn)行拆分,然后調(diào)用合并* @param arr 原數(shù)組* @param i 拆分左邊界* @param j 拆分右邊界* @param temp 緩沖數(shù)組*/private static void merge(int[] arr, int l, int r, int[] temp) {if(l<r){//取出中間值int mid=(l+r)/2;//拆分左面merge(arr,l,mid,temp);//拆分右面merge(arr,mid+1,r,temp);//合并mergeSort(arr,l,mid,r,temp);System.out.println(Arrays.toString(arr));}}/*** 合并* @param arr 要合并的數(shù)組* @param l 要合并的左面開始位置* @param mid 要合并的中間位置* @param r 要合并的結(jié)束位置* @param temp 緩沖數(shù)組*/private static void mergeSort(int[] arr, int l, int mid, int r, int[] temp) {int left=l; //要合并的左面數(shù)組的起始位置int right=mid+1; //要合并的右面數(shù)組的起始位置int index=l; //temp中存儲數(shù)據(jù)的索引位置//一、將兩個數(shù)組按大小順序復(fù)制到temp數(shù)組中//有兩個數(shù)組要合并 一個數(shù)組的位置為 [l,mid] 另一個數(shù)組的位置為[mid+1,r] while(left<=mid && right<=r){if(arr[left]<=arr[right]){temp[index]=arr[left];//緩存數(shù)組索引加1index++;//本數(shù)組索引加1left++;}else{temp[index]=arr[right];//緩存數(shù)組索引加1index++;//本數(shù)組索引加1right++;}}//將剩余的數(shù)組放到緩沖數(shù)組中while(left<=mid){temp[index]=arr[left];index++;left++;}while(right<=r){temp[index]=arr[right];index++;right++;}//二、將temp數(shù)組中的值替換給arr原數(shù)組中for(int i=l;i<=r;i++){arr[i]=temp[i];}} }

快速排序

思想
采用分治思想
1.首先選取一個基準(zhǔn)數(shù)
2.將小于基準(zhǔn)數(shù)的數(shù)放倒基準(zhǔn)數(shù)的左面
3.將大于基準(zhǔn)數(shù)的數(shù)放到基準(zhǔn)數(shù)的右面
4.一次遞歸拆分，直到數(shù)組有序
圖解
1.首先選取一個基準(zhǔn)數(shù)，這里選擇基準(zhǔn)數(shù)為19
設(shè)置最左面的位置為L
設(shè)置最右面的位置為R

2.將R處索引中的8和基準(zhǔn)數(shù)進(jìn)行比較，由于比基準(zhǔn)數(shù)小則將8放到L索引處位置，
同時L索引后移一位

3.將L處索引數(shù)值取出和基準(zhǔn)數(shù)比較，由于比基準(zhǔn)數(shù)大，將97放到R處索引位置，同時R索引前移一位

4.將R處索引上的值和基準(zhǔn)數(shù)比較，由于1比基準(zhǔn)數(shù)小，將1放到L索引位置，同時L的索引后移1位

5.將L索引處的數(shù)和基準(zhǔn)數(shù)比較，由于9比基準(zhǔn)數(shù)小，L直接后移一位
將L索引處的數(shù)和基準(zhǔn)數(shù)比較，由于17比基準(zhǔn)數(shù)小，L直接后移一位

6.在L和R重合了，這時將基準(zhǔn)數(shù)插入到重合的位置，得到第一次排序

代碼

public class QuickSort {public static void main(String[] args) {int[] arr={-9,78,0,23,-567,70};quickSort(arr,0,arr.length-1);System.out.println(Arrays.toString(arr));}private static void quickSort(int[] arr, int left, int right) {//要將所有的操作放到這個判斷中,如果在這個判斷外遞歸會出現(xiàn)死循環(huán)if(left<right){//選取一個基準(zhǔn)數(shù)int pivot=arr[left];int l=left;int r=right;while (l < r){//從右往左找到一個小于基準(zhǔn)數(shù)的數(shù),沒有找到的話R左移一位while(l<r && arr[r]>pivot){r--;}//將這個數(shù)插入到 L索引處，同時L索引坐標(biāo)右移一位if(l<r){arr[l]=arr[r];l++;}//從左往右找到一個大于基準(zhǔn)數(shù)的數(shù),沒有找到的話L右移一位while(l<r && arr[l]<pivot){l++;}//將這個數(shù)插入到 R索引處，同時R索引坐標(biāo)左移一位if(l<r){arr[r]=arr[l];r--;}}//當(dāng)L=R時將基準(zhǔn)數(shù)插入到這個位置arr[l]=pivot;System.out.println(Arrays.toString(arr));quickSort(arr,left,l-1);quickSort(arr,l+1,right);}} }

總結(jié)

以上是生活随笔為你收集整理的八大排序-志宇的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。