摘要：一常見的排序算法及時(shí)間復(fù)雜度二各排序算法的理解及實(shí)現(xiàn)冒泡排序算法描述比較相鄰元素，如果第一個(gè)比第二個(gè)大，交換位置，這樣每經(jīng)過一趟就冒出一個(gè)最大的動(dòng)圖演示代碼實(shí)現(xiàn)快速排序算法描述從數(shù)列中挑出一個(gè)元素，稱為基準(zhǔn)從左向右找比這個(gè)第一個(gè)比這個(gè)基

（1）算法描述

比較相鄰元素，如果第一個(gè)比第二個(gè)大，交換位置，這樣每經(jīng)過一趟就冒出一個(gè)最大的

（2）動(dòng)圖演示

（3）代碼實(shí)現(xiàn)

 public static int[] bubbleSort(int arr[]){
        int len = arr.length;
       for(int i = 0;iarr[j+1]){
                   int temp = arr[j];
                   arr[j] = arr[j+1];
                   arr[j+1] = temp;
               }
           }
       }
       return arr;
    }

（1）算法描述

從數(shù)列中挑出一個(gè)元素，稱為"基準(zhǔn)"（pivot）

從左向右找比這個(gè)第一個(gè)比這個(gè)基準(zhǔn)大的數(shù)，從右往左找第一個(gè)比這個(gè)基準(zhǔn)小的數(shù)，找到后互換位置

繼續(xù)在此基礎(chǔ)上執(zhí)行第二步，直到兩個(gè)尋找指針相遇

遞歸的（recursive）把小于基準(zhǔn)值的序列和大于基準(zhǔn)值的序列排序

（2）動(dòng)圖演示

 public static void quickSort(int[]arr, int left,int right) {
        if(left>right){return; }//遞歸的出口
        int i = left,j = right;
        int pivot = arr[left];//找到基準(zhǔn)
        while (i < j) {
            //從右向左找第一個(gè)比基準(zhǔn)值小的數(shù)
            while (i < j && arr[j] >= pivot) {
                j--;
            }
            //從左向右找第一個(gè)比基準(zhǔn)值大的數(shù)
            while (i < j && arr[i] <= pivot) {
                i++;
            }

            //兩面都找到后互換位置
            if (i < j) {
                int tmp = arr[i];
                arr[i] = arr[j];
                arr[j] = tmp;
            }
        }
        //left=right時(shí)于基準(zhǔn)值互換
        int tmp = arr[j];
        arr[j] = arr[left];
        arr[left] = tmp;
        //分別遞歸的調(diào)用基準(zhǔn)值的左邊和右邊
        quickSort(arr,left,i-1);
        quickSort(arr,i+1,right);

    }

（1）算法描述

從第二個(gè)元素開始（因?yàn)檎J(rèn)為第一個(gè)元素已經(jīng)有序）向前掃描

如果前一個(gè)數(shù)小于當(dāng)前元素，繼續(xù)跳到下一個(gè)元素開始向前掃描

如果前一個(gè)數(shù)大于當(dāng)前元素，繼續(xù)向前掃描，直到找到小于這個(gè)數(shù)的元素，插到它的后面

（2）動(dòng)圖演示

（3）代碼實(shí)現(xiàn)

  public static void insertSort(int[] array){
        int len = array.length;
        for(int i = 1;i0 && array[j-1]>temp;j--){
                //如果比待插入數(shù)大 ，向右移
                array[j] = array[j-1];
            }
            //如果比帶插入數(shù)小，插在該數(shù)后面
            array[j] = temp;
        }

（1）算法描述

其實(shí)就是對(duì)插入排序進(jìn)行了優(yōu)化，先對(duì)相同間隔的一組數(shù)進(jìn)行插入排序，使序列基本有序，再進(jìn)行間隔為1的插入排序時(shí)，減少工作量。（代碼實(shí)現(xiàn)可對(duì)照插入排序，其實(shí)就是多了一組循環(huán)）

（2）動(dòng)圖演示

（3）代碼實(shí)現(xiàn)

 public static void shellSort(int[] array){
        int len= array.length;
        int gap;//增量長(zhǎng)度
        for(gap = len/2;gap>0;gap/=2){
            for(int i = gap;i gap && array[j - gap] > temp; j-=gap) {
                    //如果比待插入數(shù)大 ，向右移
                    array[j] = array[j - gap];
                }
                //如果比待插入數(shù)小，插在該數(shù)后面
                array[j] = temp;
            }
        }
    }

（1）算法描述

將序列劃分為有序區(qū)和無(wú)序區(qū)（初始狀態(tài)有序區(qū)為空）

遍歷無(wú)序區(qū)，選出最小的元素，放到有序區(qū)

（2）動(dòng)圖演示

（3）代碼實(shí)現(xiàn)

   public static int[] selectSort(int array[]){
        for(int i=0;i
6.堆排序
（1）算法描述