排序算法

一、冒泡排序

其实现原理是重复扫描待排序序列，并比较每一对相邻的元素，当该对元素顺序不正确时进行交换。一直重复这个过程，直到没有任何两个相邻元素可以交换，就表明完成了排序。复杂度为 2^n

for(i = nums.length-1; i>0; i--){
    for(j = 0; j<i; j++){
        if(nums[j] > nums[j+1]){
            int temp = nums[j];
            nums[j] = nums[j+1];
            nums[j+1] = temp;
        }        
    }
}

二、快速排序

快速排序是冒泡排序的一种优化。

/*
 * 快速排序
 *
 * 参数说明：
 *     a -- 待排序的数组
 *     l -- 数组的左边界(例如，从    +-起始位置开始排序，则l=0)
 *     r -- 数组的右边界(例如，排序截至到数组末尾，则r=a.length-1)
 */
void quick_sort(int a[], int l, int r)
{
    if (l < r)
    {
        int i,j,x;

        i = l;
        j = r;
        x = a[i];
        while (i < j)
        {
            while(i < j && a[j] > x)
                j--; // 从右向左找第一个小于x的数
            if(i < j)
                a[i++] = a[j];
            while(i < j && a[i] < x)
                i++; // 从左向右找第一个大于x的数
            if(i < j)
                a[j--] = a[i];
        }
        a[i] = x;
        quick_sort(a, l, i-1); /* 依据a[i]分为左边并对左边进行递归调用 */
        quick_sort(a, i+1, r); /* 依据a[i]分为右边并对右边进行递归调用 */
    }
}

三、选择排序

选择排序(Selection sort)是一种简单直观的排序算法。其基本思想是：首先在未排序的数列中找到最小(or最大)元素，然后将其存放到数列的起始位置；接着，再从剩余未排序的元素中继续寻找最小(or最大)元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

选择排序的时间复杂度是 n^2 ：假设被排序的数列中有N个数。遍历一趟的时间复杂度是O(N)，需要遍历多少次呢？N-1次因此，选择排序的时间复杂度是 n^2 。

选择排序是稳定的算法，它满足稳定算法的定义：假设在数列中存在a[i]=a[j]，若在排序之前，a[i]在a[j]前面；并且排序之后，a[i]仍然在a[j]前面。则这个排序算法是稳定的！

引用于：通俗易懂讲解 选择排序 - 忆臻的文章 - 知乎 https://zhuanlan.zhihu.com/p/29889599

/* * 选择排序 * 
 * 参数说明： 
 *     a -- 待排序的数组 
 *     n -- 数组的长度 
 */

void select_sort(int a[], int n)
{
    int i;        // 有序区的末尾位置
    int j;        // 无序区的起始位置
    int min;    // 无序区中最小元素位置

    for(i=0; i<n; i++)
    {
        min=i;

        //找"a[i+1]..a[n]"之间最小元素，并赋给min
        for(j=i+1; j<n; j++)
        {
            if(a[j] < a[min])
                min=j;
        }

        //若min!=i，则交换 a[i] 和 a[min]。
        //交换后，保证了a[0]..a[i]之间元素有序。
        if(min != i)
            swap(a[i], a[min]);
    }
}

四、归并排序

把两个或多个已经有序的序列合并成一个，时间复杂度O(nlog n)，空间复杂度O(n)，归并排序是稳定的。

int *B = (int *)malloc(n*sizeof(int));//辅助函数B

//A[low_mid]和A[mid+1...high]各自有序，将两个部分归并
void Merge(int A[],int low,int mid,int high){
    int i,j,k;
    //复制数组
    for(k = low;k<=high;k++)
        B[k] = A[k];
    //选择判断排序    
    for(i=low,j=mid+1,k=i;i<=mid&&j<=high;k++){
        if(B[i]<=B[j]){
            A[k] = B[i++];
        }else{
            A[k] = B[j++];
        }
    }
    //对剩下部分有序序列进行复制
    while(i<=mid) A[k++] = B[i++];
    while(i<=high) A[k++] = B[j++];
}

//使用递归的方式调用
void MergeSort(int A[],int low,int high){
    if(low<high){
        int mid = (low + high)/2;
        MergeSort(A,low,mid);//对左半部分归并排序
        MergeSort(A,mid+1,high);//对右半部分归并排序
        Merge(A,low,mid,high);//归并
    }
}

五、插入排序

插入排序的平均时间复杂度也是 O(n^2)，空间复杂度为常数阶 O(1)，具体时间复杂度和数组的有序性也是有关联的。

判断当前数值与前一个数值的大小，如果小于则替换，一直循环比较并替换完成最小的值，然后进入下一次循环。

for (int i = 0; i < n; i++) {
    // 寻找元素 arr[i] 合适的插入位置
   for( int j = i ; j > 0 ; j -- )
        if( arr[j].compareTo( arr[j-1] ) < 0 )//arr[j] < arr[j-1]
            swap( arr, j , j-1 );
        else
            break;
}

private static void swap(Object[] arr, int i, int j) {
        Object t = arr[i];
        arr[i] = arr[j];
        arr[j] = t;
}