排序算法详解和代码示例
1. 快速排序

介绍：快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下，排序 n 个项目要Ο(n log n)次比较。在最坏状况下则需要Ο(n2)次比较，但这种状况并不常见。
事实上，快速排序通常明显比其他Ο(n log n) 算法更快，因为它的内部循环（inner loop）可以在大部分的架构上很有效率地被实现出来，且在大部分真实世界的数据，可以决定设计的选择，减少所需时间的二次方项之可能性。

步骤：

从数列中挑出一个元素，称为 “基准”（pivot），
重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。
递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。
示例代码：
//a：待排序数组，low：最低位的下标，high：最高位的下标
void quickSort(int a[],int low, int high)
{
    if(low>=high)
    {
        return;
    }
    int left=low;
    int right=high;
    int key=a[left];    /*用数组的第一个记录作为分区元素*/
    while(left!=right){
        while(left<right&&a[right]>=key)    /*从右向左扫描，找第一个码值小于key的记录，并交换到key*/
            --right;
        a[left]=a[right];
        while(left<right&&a[left]<=key)
            ++left;
        a[right]=a[left];    /*从左向右扫描，找第一个码值大于key的记录，并交换到右边*/
    }
    a[left]=key;    /*分区元素放到正确位置*/
    quickSort(a,low,left-1);
    quickSort(a,left+1,high);
}
 

2. 归并排序

介绍：

归并排序（Merge sort，台湾译作：合并排序）是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用

步骤：

申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
设定两个指针，最初位置分别为两个已经排序序列的起始位置
比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
重复步骤3直到某一指针达到序列尾
将另一序列剩下的所有元素直接复制到合并序列尾
代码示例:

public class MergeSort { 
    /**
     * 归并排序
     * 简介:将两个（或两个以上）有序表合并成一个新的有序表 即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列
     * 时间复杂度为O(nlogn)
     * 稳定排序方式
     * @param nums 待排序数组
     * @return 输出有序数组
     */ 
    public static int[] sort(int[] nums, int low, int high) { 
        int mid = (low + high) / 2; 
        if (low < high) { 
            // 左边 
            sort(nums, low, mid); 
            // 右边 
            sort(nums, mid + 1, high); 
            // 左右归并 
            merge(nums, low, mid, high); 
        } 
        return nums; 
    } 
 
    public static void merge(int[] nums, 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 (nums[i] < nums[j]) { 
                temp[k++] = nums[i++]; 
            } else { 
                temp[k++] = nums[j++]; 
            } 
        } 
 
        // 把左边剩余的数移入数组 
        while (i <= mid) { 
            temp[k++] = nums[i++]; 
        } 
 
        // 把右边边剩余的数移入数组 
        while (j <= high) { 
            temp[k++] = nums[j++]; 
        } 
 
        // 把新数组中的数覆盖nums数组 
        for (int k2 = 0; k2 < temp.length; k2++) { 
            nums[k2 + low] = temp[k2]; 
        } 
    } 
 
     
    // 归并排序的实现 
    public static void main(String[] args) { 
 
        int[] nums = { 2, 7, 8, 3, 1, 6, 9, 0, 5, 4 }; 
 
        MergeSort.sort(nums, 0, nums.length-1); 
        System.out.println(Arrays.toString(nums)); 
    } 
}
 

3. 堆排序

介绍：堆积排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构，并同时满足堆性质：即子结点的键值或索引总是小于（或者大于）它的父节点。

步骤：

（1）性质：完全二叉树或者是近似完全二叉树；
（2）分类：大顶堆：父节点不小于子节点键值，小顶堆：父节点不大于子节点键值；图展示一个最小堆：
（3）左右孩子：没有大小的顺序。
（4）堆的存储 一般都用数组来存储堆，i结点的父结点下标就为(i–1)/2。它的左右子结点下标分别为 2∗i+1 和 2∗i+2。如第0个结点左右子结点下标分别为1和2。
（5）堆的操作
示例代码：
 //新加入i结点,其父结点为(i-1)/2
//参数：a：数组，i：新插入元素在数组中的下标 
void minHeapFixUp(int a[], int i) 
{ 
    int j, temp; 
    temp = a[i]; 
    j = (i-1)/2;      //父结点 
    while (j >= 0 && i != 0) 
    { 
        if (a[j] <= temp)//如果父节点不大于新插入的元素，停止寻找 
            break; 
        a[i]=a[j];     //把较大的子结点往下移动,替换它的子结点 
        i = j; 
        j = (i-1)/2; 
    } 
    a[i] = temp; 
}
//在最小堆中加入新的数据data 
//a：数组，index：插入的下标，
void minHeapAddNumber(int a[], int index, int data) 
{ 
    a[index] = data; 
    minHeapFixUp(a, index); 
}

4. 选择排序

介绍：选择排序(Selection sort)是一种简单直观的排序算法。它的工作原理如下。首先在未排序序列中找到最小元素，存放到排序序列的起始位置，然后
再从剩余未排序元素中继续寻找最小元素，然后放到排序序列末尾。以此类推，直到所有元素均排序完毕。
代码示例：
/**
 * 选择排序
 *
 */ 
void selectSort(int a[], int n){ 
    int key, tmp; 
    for(int i = 0; i< n; ++i) { 
        key = SelectMinKey(a, n,i);           //选择最小的元素 
        if(key != i){ 
            tmp = a[i];  a[i] = a[key]; a[key] = tmp; //最小元素与第i位置元素互换 
        } 
        print(a,  n , i); 
    } 
} 
int main(){ 
    int a[8] = {3,1,5,7,2,4,9,6}; 
    cout<<"初始值："; 
    for(int j= 0; j<8; j++){ 
        cout<<a[j] <<"  "; 
    } 
    cout<<endl<<endl; 
    selectSort(a, 8); 
    print(a,8,8); 
} 

 

5. 冒泡排序

介绍：冒泡排序（Bubble Sort，台湾译为：泡沫排序或气泡排序）是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，
如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

步骤：

比较相邻的元素。如果第一个比第二个大，就交换他们两个。
对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
针对所有的元素重复以上的步骤，除了最后一个。
持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
代码示例：
public class bubbleSort { 
public  bubbleSort(){ 
     int a[]={49,38,65,97,76,13,27,49,78,34,12,64,5,4,62,99,98,54,56,17,18,23,34,15,35,25,53,51}; 
    int temp=0; 
    for(int i=0;i<a.length-1;i++){ 
        for(int j=0;j<a.length-1-i;j++){ 
        if(a[j]>a[j+1]){ 
            temp=a[j]; 
            a[j]=a[j+1]; 
            a[j+1]=temp; 
        } 
        } 
    } 
    for(int i=0;i<a.length;i++) 
        System.out.println(a[i]);    
} 
} 

 

6. 插入排序

介绍：插入排序（Insertion Sort）的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，
找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。

步骤：

从第一个元素开始，该元素可以认为已经被排序
取出下一个元素，在已经排序的元素序列中从后向前扫描
如果该元素（已排序）大于新元素，将该元素移到下一位置
重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
将新元素插入到该位置中
代码示例：

public static void InsertSort(int[] arr)
{
    int i, j;
    int n = arr.Length;
    int target;
 
    //假定第一个元素被放到了正确的位置上
    //这样，仅需遍历1 - n-1
    for (i = 1; i < n; i++)
    {
        j = i;
        target = arr[i];
 
        while (j > 0 && target < arr[j - 1])
        {
            arr[j] = arr[j - 1];
            j--;
        }
 
        arr[j] = target;
    }
}

 

7. 希尔排序

介绍：

希尔排序，也称递减增量排序算法，是插入排序的一种高速而稳定的改进版本。

希尔排序是基于插入排序的以下两点性质而提出改进方法的：

1、插入排序在对几乎已经排好序的数据操作时， 效率高， 即可以达到线性排序的效率

2、但插入排序一般来说是低效的， 因为插入排序每次只能将数据移动一位
代码示例：

public static void shellSortSmallToBig(int[] data) {
        int j = 0;
        int temp = 0;
        for (int increment = data.length / 2; increment > 0; increment /= 2) {
            System.out.println("increment:" + increment);
            for (int i = increment; i < data.length; i++) {
                // System.out.println("i:" + i);
                temp = data[i];
                for (j = i - increment; j >= 0; j -= increment) {
                    // System.out.println("j:" + j);
                    // System.out.println("temp:" + temp);
                    // System.out.println("data[" + j + "]:" + data[j]);
                    if (temp < data[j]) {
                        data[j + increment] = data[j];
                    } else {
                        break;
                    }
                }
                data[j + increment] = temp;
            }
            for (int i = 0; i < data.length; i++)
                System.out.print(data[i] + " ");
        }
    }

    public static void main(String[] args) {
        int[] data = new int[] { 26, 53, 67, 48, 57, 13, 48, 32, 60, 50 };
        shellSortSmallToBig(data);
        System.out.println(Arrays.toString(data));
    }