排序算法大全

package cn.baidu;

import java.util.Arrays;

public class SortTest {

    public static void main(String[] args) {
        int[] arr = { 2, 5, 3, 1, 4 };
        System.out.println("排序前：" + Arrays.toString(arr));
        // InsertSort.sort(arr);
        // BubbleSort.sort(arr);
        // SelectionSort.sort(arr);
        // ShellSort.sort(arr);
        // QuickSort.sort(arr);
        // MergeSort.sort(arr);
        // HeapSort.sort(arr);
        System.out.println("排序后：" + Arrays.toString(arr));
    }

    /*
     * 交換數(shù)組中的兩個元素
     */
    public static void swap(int[] data, int i, int j) {
        int temp = data[i];
        data[i] = data[j];
        data[j] = temp;
    }
}

 /**
     * 冒泡排序(穩(wěn)定)
     * @param array
     
     冒泡排序(Bubble Sort)也是一種簡單直觀的排序算法.它重復(fù)地走訪過要排序的數(shù)列,一次比較兩個元素,
     如果他們的順序錯誤就把他們交換過來.走訪數(shù)列的工作是重復(fù)地進行直到?jīng)]有再需要交換,也就是說該數(shù)列已經(jīng)排序完成.
     這個算法的名字由來是因為越小的元素會經(jīng)由交換的慢"浮"到數(shù)列的頂端.
     
     算法步驟 :
        1: 比較相鄰的元素.如果第一個比第二個大,就交換他們兩個.
        2: 對每一對相鄰元素作同樣的工作,從開始第一對到結(jié)尾的最后一對.這步做完后,最后的元素會是最大的數(shù).
        3: 針對所有的元素重復(fù)以上的步驟,除了最后一個.
        4: 持續(xù)每次對越來越少的元素重復(fù)上面的步驟,直到?jīng)]有任何一對數(shù)字需要比較.
     
     
     */
    public static void bubbleSort(int[] array){
        for (int i = 0; i < array.length - 1; i++) {
            for (int j = 0; j < (array.length - 1 - i); j++) {
                if(array[j] > array[j+1]){
                    swap(array, j, j+1);
                }
            }
            System.out.println(Arrays.toString(array));
        }
    }

package cn.baidu;

/*
 * 插入排序基本思想
 * 將n個元素的數(shù)列分為已有序和無序兩個部分，如插入排序過程示例下所示： 　　
 * {{a1}，{a2，a3，a4，…，an}} 　　
 * {{a1⑴，a2⑴}，{a3⑴，a4⑴ …，an⑴}} 　
 * {{a1(n-1），a2(n-1) ，…},{an(n-1)}} 　　
 * 每次處理就是將無序數(shù)列的第一個元素與有序數(shù)列的元素從后往前逐個進行比較，
 * 找出插入位置，將該元素插入到有序數(shù)列的合適位置中。
 
 插入排序是一種罪簡單直觀的排序算法,它的工作原理是通過構(gòu)建有序序列,對于未排序數(shù)據(jù),在已排序序列中從后向前掃描,
 找到相應(yīng)位置并插入.
 
 算法步驟 :
    1: 將第一待排序序列第一個元素看做一個有序序列,把第二個元素到最后一個元素當成是末排序序列.
    2: 從頭到尾依次掃描未排序序列,將掃描到的每個元素插入有序序列的適當位置.(如果待插入的元素與有序序列中的某個元素相等
    ,則將待插入元素插入到相等元素的后面.
 
 
 */
public class InsertSort {
    public static void sort(int[] data) {
        for (int i = 1; i < data.length; i++) {
            for (int j = i; (j > 0) && (data[j] < data[j - 1]); j--) {
                SortTest.swap(data, j, j - 1);
            }
        }

    }
}

/*
 * 選擇排序基本思路：
 * 把第一個元素依次和后面的所有元素進行比較。
 * 第一次結(jié)束后，就會有最小值出現(xiàn)在最前面。
 * 依次類推
 選擇排序(Selection sort)也是一種簡單直觀的排序算法
 
 算法步驟 :
    1: 首先在末排序序列中找到最小(最大)元素,存放到排序序列的起始位置.
    2: 再從剩余末排序元素中繼續(xù)尋找最小(大)元素,然后放到已排序序列的末尾
    3: 重復(fù)第二步,直到所有元素均排序完畢.
 
 */
public class SelectionSort {
    public static void sort(int[] data) {
        for (int x = 0; x < data.length - 1; x++) {
            for (int y = x + 1; y < data.length; y++) {
                if (data[y] < data[x]) {
                    SortTest.swap(data, x, y);
                }
            }
        }
    }
}
  /**
     * 快速排序（不穩(wěn)定）: 所謂的不穩(wěn)定是當兩個相同的數(shù)字在數(shù)組中的時候,會出現(xiàn)一種情況,就是把這兩個相同的數(shù)給交換了位置.
     * @param array
     快速排序是由東尼·霍爾所發(fā)展的一種排序算法。在平均狀況下，排序 n 個項目要Ο(n log n)次比較。在最壞狀況下則需要Ο(n2)次比較，但這種狀況并不常見。事實上，快速排序通常明顯比其他Ο(n log n) 算法更快，因為它的內(nèi)部循環(huán)（inner loop）可以在大部分的架構(gòu)上很有效率地被實現(xiàn)出來。
    快速排序使用分治法（Divide and conquer）策略來把一個串行（list）分為兩個子串行（sub-lists）。

    算法步驟：
    1 從數(shù)列中挑出一個元素，稱為 “基準”（pivot），
    2 重新排序數(shù)列，所有元素比基準值小的擺放在基準前面，所有元素比基準值大的擺在基準的后面（相同的數(shù)可以到任一邊）。在這個分區(qū)退出之后，該基準就處于數(shù)列的中間位置。這個稱為分區(qū)（partition）操作。
    3 遞歸地（recursive）把小于基準值元素的子數(shù)列和大于基準值元素的子數(shù)列排序。

    遞歸的最底部情形，是數(shù)列的大小是零或一，也就是永遠都已經(jīng)被排序好了。雖然一直遞歸下去，但是這個算法總會退出，因為在每次的迭代（iteration）中，它至少會把一個元素擺到它最后的位置去。
         
     */
    public static void quickSort(int[] array){
        quickSort(array, 0, array.length - 1);
    }

    private static void quickSort(int[] array, int low, int high) {
        int i = low, j = high;
        int pivot = array[(low + high)/2];//中間位置值
        while (i <= j){
            while(array[i] < pivot){
                i++;
            }
            while(array[j] > pivot){
                j--;
            }

            if(i <= j){
                swap(array, i, j);
                i++;
                j--;
            }
        }
        if(i < high){
            quickSort(array, i, high);
        }
        if(j > low){
            quickSort(array, low, j);
        }
    }

    /**
     * 交換數(shù)組值
     * @param array
     * @param i
     * @param j
     */
    private static void swap(int[] array, int i, int j) {
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }
}

package com.dn.sort;


public class BinaryInsertSort {
    public static void main(String[] args) {
        int[] a={49,38,65,97,176,213,227,49,78,34,12,164,11,18,1};
        System.out.println("排序之前：");
        for (int i = 0; i < a.length; i++) {
            System.out.print(a[i]+" ");
        }
        //二分插入排序
        sort(a);
        System.out.println();
        System.out.println("排序之后：");
        for (int i = 0; i < a.length; i++) {
            System.out.print(a[i]+" ");
        }
    }
//二分法插入
    private static void sort(int[] a) {
        for (int i = 0; i < a.length; i++) {
            int temp = a[i];
            int left = 0;
            int right = i-1;
            int mid = 0;
            //確定要插入的位置
            while(left<=right){
                //先獲取中間位置
                mid = (left+right)/2;
                if(temp<a[mid]){
                    //如果值比中間值小，讓right左移到中間下標-1
                    right = mid-1;
                }else{
                    //如果值比中間值大,讓left右移到中間下標+1
                    left = mid+1;
                }
            }
            for (int j = i-1; j >= left; j--) {
                //以左下標為標準，在左位置前插入該數(shù)據(jù)，左及左后邊全部后移
                a[j+1] = a[j];
            }
            if(left != i){
                //左位置插入該數(shù)據(jù)
                a[left] = temp;
            }
        }
    }
}

package com.dn.sort;

public class InsertSort {
/**
 * 直接插入排序
 * @param args
 */
        public static void main(String[] args) {
            int[] a={49,38,65,97,76,13,27,49,78,34,12,64,1};
            System.out.println("排序之前：");
            for (int i = 0; i < a.length; i++) {
                System.out.print(a[i]+" ");
            }
            //直接插入排序
            for (int i = 1; i < a.length; i++) {
                //待插入元素
                int temp = a[i];
                int j;
                for (j = i-1; j>=0; j--) {
                    //將大于temp的往后移動一位
                    if(a[j]>temp){
                        a[j+1] = a[j];
                    }else{
                        break;
                    }
                }
                a[j+1] = temp;//插入進來
            }
            System.out.println();
            System.out.println("排序之后：");
            for (int i = 0; i < a.length; i++) {
                System.out.print(a[i]+" ");
            }
        }
}