八大排序算法

一儒恋、歸并排序

遞歸及非遞歸的JAVA實(shí)現(xiàn)

public static void MergeSort(int[] arr, int low, int high)
{
    //使用遞歸的方式進(jìn)行歸并排序弊予，所需要的空間復(fù)雜度是O（N+logN）
    int mid = (low + high)/2;
    if(low < high)
    {
        //遞歸地對(duì)左右兩邊進(jìn)行排序
        MergeSort(arr, low, mid);
        MergeSort(arr, mid+1, high);
        //合并
        merge(arr, low, mid, high);
    }
}

//merge函數(shù)實(shí)際上是將兩個(gè)有序數(shù)組合并成一個(gè)有序數(shù)組
//因?yàn)閿?shù)組有序嚷硫，合并很簡(jiǎn)單宣蠕，只要維護(hù)幾個(gè)指針就可以了
private static void merge(int[] arr, int low, int mid, int high)
{
    //temp數(shù)組用于暫存合并的結(jié)果
    int[] temp = new int[high - low + 1];
    //左半邊的指針
    int i = low;
    //右半邊的指針
    int j = mid+1;
    //合并后數(shù)組的指針
    int k = 0;
    
    //將記錄由小到大地放進(jìn)temp數(shù)組
    for(; i <= mid && j <= high; k++)
    {
        if(arr[i] < arr[j])
            temp[k] = arr[i++];
        else
            temp[k] = arr[j++];
    }
    
    //接下來兩個(gè)while循環(huán)是為了將剩余的（比另一邊多出來的個(gè)數(shù)）放到temp數(shù)組中
    while(i <= mid)
        temp[k++] = arr[i++];
    
    while(j <= high)
        temp[k++] = arr[j++];
    
    //將temp數(shù)組中的元素寫入到待排數(shù)組中
    for(int l = 0; l < temp.length; l++)
        arr[low + l] = temp[l];
}

二搁胆、快速排序

快排算法JAVA實(shí)現(xiàn)

/**
 * 快速排序
 * 基本思想:
 * 1.在待排序的元素任取一個(gè)元素作為基準(zhǔn)(通常選第一個(gè)元素弥搞，但最佳選擇方法是從待排序元素中隨機(jī)選取一個(gè)作為基準(zhǔn))，稱為基準(zhǔn)元素渠旁；
 * 2.將待排序的元素進(jìn)行分區(qū)攀例，比基準(zhǔn)元素大的元素放在它的右邊，比其小的放在它的左邊顾腊；
 * 3.對(duì)左右兩個(gè)分區(qū)重復(fù)以上步驟直到所有元素都是有序的粤铭。
 */
public void quick_sort(int[] arr,int _left,int _right){
    int left=_left;
    int right=_right;
    int temp=0;
    //待排序元素至少有1個(gè)
    if(left<=right){
       temp=arr[left]; //待排序的第一個(gè)元素作為基準(zhǔn)元素
        while(left!=right){ //從左右兩邊交替掃描，直到left = right

            while(right>left && arr[right]>=temp)
                right--;  //從右往左掃描杂靶，找到第一個(gè)比基準(zhǔn)元素小的元素
            arr[left]=arr[right]; //找到這種元素arr[right]后與arr[left]交換

            while(left<right && arr[left]<=temp)
                left++;   //從左往右掃描梆惯，找到第一個(gè)比基準(zhǔn)元素大的元素
            arr[right]=arr[left]; //找到這種元素arr[left]后，與arr[right]交換
        }
        arr[right]=temp; // 基準(zhǔn)元素歸位
        quick_sort(arr,_left,left-1); //對(duì)基準(zhǔn)元素左邊的元素進(jìn)行遞歸排序
        quick_sort(arr,right+1,_right); //對(duì)基準(zhǔn)元素右邊的進(jìn)行遞歸排序
    }
}

三吗垮、堆排序

堆排序
堆排序算法JAVA實(shí)現(xiàn)

/**
 * 堆排序
 * 基本思想：
 * 首先垛吗，堆分為最大堆和最小堆，最大堆則是指在一棵樹中烁登，父結(jié)點(diǎn)總是比子結(jié)點(diǎn)大怯屉，堆頂是整棵樹中的最大值，
 * 同樣的最小堆則是父結(jié)點(diǎn)都比子結(jié)點(diǎn)要小饵沧，堆頂則是最小值锨络。
 *
 * 排序的過程則是將數(shù)組根據(jù)要排列的順序去決定是排最大堆還是最小堆，建完堆以后將堆頂?shù)闹等〕龊螅? * 重新將堆進(jìn)行調(diào)整狼牺，調(diào)整后的值同樣滿足堆的性質(zhì)羡儿，接著再取出，以此類推是钥。
 */
/**
 * (最大)堆的向下調(diào)整算法
 * 注：數(shù)組實(shí)現(xiàn)的堆中掠归，第N個(gè)節(jié)點(diǎn)的左孩子的索引值是(2N+1)，右孩子的索引是(2N+2)悄泥。
 * 其中拂到，N為數(shù)組下標(biāo)索引值，如數(shù)組中第1個(gè)數(shù)對(duì)應(yīng)的N為0码泞。
 * @param arr
 * @param start
 * @param end
 */
public void maxHeapDown(int[] arr,int start,int end){
    int current=start; //當(dāng)前節(jié)點(diǎn)位置兄旬，即父親節(jié)點(diǎn)
    int left=2*current+1; //左孩子的位置
    while(left<=end){ //子節(jié)點(diǎn)在范圍內(nèi)才進(jìn)行調(diào)整
        //選擇子節(jié)點(diǎn)中大的值
        if(left+1<=end && arr[left]<arr[left+1])
            left++;
        if(arr[current]>arr[left])
            break; //調(diào)整結(jié)束
        else{  //否則繼續(xù)和孫節(jié)點(diǎn)進(jìn)行比較
            swap(arr,current,left);
            current=left;
            left=2*current+1;
        }
    }
}

public void heap_sort(int[] arr,int len){
    //初始化，從i最后一個(gè)父親節(jié)點(diǎn)開始調(diào)整
    for(int i=len/2-1;i>=0;i--)
        maxHeapDown(arr,i,len-1);
    //先將第一個(gè)元素和后面的元素進(jìn)行交換，再調(diào)整
    for(int i=len-1;i>0;i--){
        swap(arr,0,i);
        maxHeapDown(arr,0,i-1);
    }
}

四领铐、冒泡排序

冒泡排序算法JAVA實(shí)現(xiàn)

  /**
 * 冒泡排序
 * 基本思想：在要排序的一組數(shù)中悯森，對(duì)當(dāng)前還未排好序的范圍內(nèi)的全部數(shù)，自上而下對(duì)相鄰的兩個(gè)數(shù)依次進(jìn)行比較和調(diào)整绪撵，
 *         讓較大的數(shù)往下沉瓢姻，較小的往上冒。即：每當(dāng)兩相鄰的數(shù)比較后發(fā)現(xiàn)它們的排序與排序要求相反時(shí)音诈，就將它們互換幻碱。
 * @param arr
 * @param len
 */
public void bubble_sort(int[] arr,int len){
    //躺數(shù)
    for(int i=0;i<len-1;i++){
        for(int j=0;j<len-1-i;j++){
            if(arr[j]>arr[j+1]){
                swap(arr,j,j+1);
            }
        }
    }
}

五、直接插入排序

直接插入排序算法JAVA實(shí)現(xiàn)

/**
 * 直接插入排序
 * 基本思想是：每次將一個(gè)待排序的記錄细溅，按其關(guān)鍵字大小插入到前面已經(jīng)排好序的子序列中的適當(dāng)位置褥傍，直到全部記錄插入完成為止。
 * 設(shè)數(shù)組為arr[0…n-1]喇聊。
 * 1.初始時(shí)恍风，arr[0]自成1個(gè)有序區(qū)，無序區(qū)為arr[1..n-1]誓篱。令i=1
 * 2.將arr[i]并入當(dāng)前的有序區(qū)arr[0…i-1]中形成arr[0…i]的有序區(qū)間朋贬。
 * 3.i++并重復(fù)第二步直到i==n-1。排序完成窜骄。
 * @param arr
 * @param len
 */
public void insert_sort(int[] arr,int len){
    int i,j;
    for(i=1;i<len;i++){
        //如果arr[i]>arr[i-1],無需調(diào)整
       if(arr[i]<arr[i-1]){
           int temp=arr[i];
           //為arr[i]找位置,找到第一個(gè)比arr[i]小的元素锦募，然后把a(bǔ)rr[i]放在其后即可
           for(j=i-1;j>=0&&arr[j]>temp;j--){
               arr[j+1]=arr[j]; //移動(dòng)
           }
           arr[j+1]=temp;
       }
   }
}

六、簡(jiǎn)單選擇排序

  /**
 * 簡(jiǎn)單選擇排序
 * 基本思想：
 * 首先在未排序序列中找到最辛诙簟（大）元素糠亩，存放到排序序列的起始位置，
 * 然后党远，再?gòu)氖Ｓ辔磁判蛟刂欣^續(xù)尋找最小（大）元素富弦，然后放到已排序序列的末尾沟娱。以此類推，直到所有元素均排序完畢腕柜。
 * @param arr
 * @param len
 */
public void select_sort(int[] arr,int len){
    for(int i=0;i<len-1;i++){
        int min=i;
        for(int j=i+1;j<len;j++){
            if(arr[j]<arr[min])
                min=j;
        }
        swap(arr,i,min);
    }
}

七济似、排序算法比較

image.png