数据结构Java版之排序算法（二）

　　排序按时间复杂度和空间复杂度可分为 低级排序 和 高级排序 算法两种。下面将对排序算法进行讲解，以及样例的展示。

低级排序：冒泡排序、选择排序、插入排序。　　

　　冒泡排序：

核心思想，小的数往前移。假设最小的数在最后一位，将最后一位一步步移到第一位。

public void bubbleSort(int[] list) {
    int n = list.length - 1;
    for(int i = 0; i < n; i ++) {
        for(int j = 0; j < n - i; j ++) {
            if(list[j] > list[j + 1])
                swap(j, j + 1, list);
        }
    }
}
public void swap(int i, int j, int[]list) {
    int temp = list[i];
    list[i] = list[j];
    list[j] = temp;
}

　　选择排序：

选择最小数按顺序排列。从当前未排序的数组中，找出一个最小的数，放在第一位。第二小的放在第二位······

public void selectSort(int[] list) {
    int min; //记录最小下标
    for(int i = 0; i < list.length - 1; i ++) {    //对n个数排序，只需将n-1个数排好序，就ok了。所以循环条件是list.length-1.
        min = i;
        for(int j = i + 1; j < list.length; j ++) {     //循环一次找出一个最小数
            if(list[j] < list[min]) {
                min = j;
            }
        }
        swap(i, min, list);
    }
}
public void swap(int i, int j, int[]list) {
    int temp = list[i];
    list[i] = list[j];
    list[j] = temp;
}

　　插入排序：

取出元素，从后往前依次比较前面的元素。直到前面的数比自己小，则插入到当前位置。在此过程中，大于或等于自己的元素一直往后移位。

public void insertSort(int[] list) {
    int sign, temp; // sign记录空值下标，temp记录取出值
    for(int i = 1; i < list.length; i ++) {
        temp = list[i];
        sign = i;
        //如果取出值小于前一个值，则把前一个值往后移，覆盖当前值
        while(sign > 0 && list[sign - 1] > temp) {
            list[sign] = list[sign - 1];
            sign --;
        }
        list[sign] = temp;
    }
}

插入排序优化写法：

//优化插入：将数组第一个元素用来保存数据，达到减少比较次数
public void insertSort_2(int[] list) {
    int sign, temp; // sign记录空值下标，temp记录取出值
    for(int i = 2; i < list.length; i ++) {
        temp = list[i];
        list[0] = temp;
        sign = i - 1;
        //如果取出值小于前一个值，则把前一个值往后移，覆盖当前值
        while(list[sign] > temp) {
            list[sign + 1] = list[sign];
            sign --;
        }
        list[sign + 1] = temp;
    }
}

高级排序：快速排序、归并排序。

public void quickSort(int left, int right, int[] list) {
    //选枢轴进行划分
    if(left < right) {
        int i = left;
        int j = right + 1;
        int privot = list[left]; //定义一个枢轴
        do{
            do{
                i ++;
            }while(list[i] < privot);//找到一个比枢轴大的数
            do{
                --j;
            }while(list[j] > privot);//找到一个比枢轴小的数
            if(i<j) swap(i, j, list);
        }while(i < j);
            
        swap(left, j, list);    //将基准数放置到中间
            
        quickSort(left, j - 1, list);
        quickSort(j + 1, right, list);
    }
}
public void swap(int i, int j, int[]list) {
    int temp = list[i];
    list[i] = list[j];
    list[j] = temp;
}

　　归并排序：

将两个排好序的数组合并在一起，并且重新排序。比如1->2>3 、1->4->5 合并在一起后就是：1->2>3 ->1->4->5  排好序为：1->1->2->3->4->5. 　　在此演示的示例为直接合并的数组。

　　首先，为方便写程序，数组第一个元素将废弃使用，不对其进行排序。

基础归并函数：归并两个排序的数组

public void Merge(int[] initList, int[] mergeList, int l, int m, int n) {    
　　 //　　initList 初始化数组， mergeList存放排好序的数组。
    //    l表示第一个数组下标，m表示第一个数组最后一个元素下标，n表示第二个数组最后一个元素下标。result表示新建数组下标
    int i1, i2, result;
    for(i1 = l, i2 = m + 1, result = i1; i1 <= m && i2 <= n; result ++) {
        if(initList[i1] <= initList[i2]) {
            mergeList[result] = initList[i1];
            i1 ++;
        }else {
            mergeList[result] = initList[i2];
            i2 ++;
        }
    }
　　//　　将第一个数组和第二个数组未放进mergeList的元素复制到mergeList中。（如果没有剩余元素，则复制元素个数为0，不产生影响，所以可以放心对两个数组都进行剩余元素复制）
    System.arraycopy(initList, i1, mergeList, result, m - i1 + 1);
    System.arraycopy(initList, i2, mergeList, result, n - i2 + 1);
}

其次，有了前面的基础归并函数，那么就可以实现乱序数组的归并排序。其思想，进行多次基础归并。

实现单次归并：划分数组进行归并。第一次单个元素作为划分对象，第二次两个元素作为划分对象·········

public void MergePass(int[] initList, int[] mergeList, int n, int s) {　　//　　n表示初始化数组最后一位元素下标，s表示第几次归并。
    int i;
    for(i = 1; i <= n - 2*s + 1; i += 2*s) { 　　//对划分的数组两两归并
        Merge(initList, mergeList, i, i + s - 1, i + 2*s - 1);
    }
        
    if((i + s - 1) < n) {　　//有剩余未归并的元素则进行归并
        Merge(initList, mergeList, i, i + s - 1, n);
    }else {　　　　//将剩余元素拷贝下来
        System.arraycopy(initList, i, mergeList, i, n + 1 - i);
    }
}

　　最后通过控制归并次数，真正达到乱序数组归并排序的效果：

public void MergeSort(int[] list) {
    int[] newList = new int[list.length];

　　for(int i = 1; i < list.length; i *= 2) {
        MergePass(list, newList, list.length - 1, i);
        i *= 2;　　　　//只所以在此进行i*2，是因为归并后的结果放在newList里面，重新进行归并时。省掉将newList重新拷贝到list的麻烦
        MergePass(newList, list, list.length - 1, i);
    }
}

接下来，来个归并算法的全家桶吧：

public class MergeSort {
    @Test
    public void fun() {
        int[] a = {0, 23, 47, 81, 95, 7, 14, 39, 55, 62, 74};
        MergeSort(a);
        for(int i : a) {
            System.out.print(i + "\t");
        }
    }
    public void Merge(int[] initList, int[] mergeList, int l, int m, int n) {    
        //    l表示第一个数组下标，m表示最后一个数组下标，result表示新建数组下标
        int i1, i2, result;
        for(i1 = l, i2 = m + 1, result = i1; i1 <= m && i2 <= n; result ++) {
            if(initList[i1] <= initList[i2]) {
                mergeList[result] = initList[i1];
                i1 ++;
            }else {
                mergeList[result] = initList[i2];
                i2 ++;
            }
        }
        System.arraycopy(initList, i1, mergeList, result, m - i1 + 1);
        System.arraycopy(initList, i2, mergeList, result, n - i2 + 1);
    }
    public void MergePass(int[] initList, int[] mergeList, int n, int s) {
        int i;
        for(i = 1; i <= n - 2*s + 1; i += 2*s) {
            Merge(initList, mergeList, i, i + s - 1, i + 2*s - 1);
        }
        
        if((i + s - 1) < n) {
            Merge(initList, mergeList, i, i + s - 1, n);
        }else {
            System.arraycopy(initList, i, mergeList, i, n + 1 - i);
        }
    }
    public void MergeSort(int[] list) {
        int[] newList = new int[list.length];
        for(int i = 1; i < list.length; i *= 2) {
            MergePass(list, newList, list.length - 1, i);
            i *= 2;
            MergePass(newList, list, list.length - 1, i);
        }
    }
}