常见的排序算法--Java/Kotlin

排序算法--快速排序
快速排序是对冒泡排序的一种改进
基本思想：通过一趟排序将要排序的数据分割成独立的两部分(分治法)，其中一部分的所有数据都比另一部分的所有数据都小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列
1.在待排序的n个记录中任意取一个记录，以改记录的排序码为准，将所有记录分为两组，一组小于，一组大于改数
2.采用相同的方法对左右两组分别进行排序，直至所有记录都排到相应位置

具体的代码(Kotlin)

private fun quickSort(q: IntArray, l: Int, r: Int) {
        if (l >= r)
            return
        val x = q[l + r shr 1]
        var i = l - 1
        var j = r + 1
        while (i < j) {
            do i++ while (q[i] < x)
            do j-- while (q[j] > x)
            if (i < j) {
                val temp = q[i]
                q[i] = q[j]
                q[j] = temp
            }
        }
        quickSort(q, l, j)
        quickSort(q, j + 1, r)
    }

具体的代码(java)

public static void quickSort( int[] q,int l,int r ){
        if(l>=r)
            return;
        int x=q[l+r>>1];
        int i=l-1;
        int j=r+1;
        while(i<j){
            do i++;while(q[i]<x);
            do j--;while(q[j]>x);
            if(i<j){
                int temp=q[i];
                q[i]=q[j];
                q[j]=temp;
            }
        }
        quickSort(q,l,j);
        quickSort(q,j+1,r);
    }

排序算法--归并排序
归并排序是建立在归并操作上的一种有效的排序算法，是采用分治法的典型应用，将已有序列的子序列合并，得到完全有序的序列
速度仅次于快速排序，是稳定的算法

示例1

在合并阶段是用两个指针来做比较，例如，我们需要将[2,5,7,8]和[1,3,4,6]合并为[1，2，3，4，5，6，7，8]

具体代码实现(kotlin)

private fun mergeSort(arr: IntArray, l: Int, r: Int) {

        if (l >= r) {
            return
        }

        val mid = l + (r - l shr 1)

        mergeSort(arr, l, mid)
        mergeSort(arr, mid + 1, r)

        val temp = IntArray(r - l + 1)
        var i = l
        var j = mid + 1
        var k = 0

        while (i <= mid && j <= r) {
            if (arr[i] <= arr[j]) {
                temp[k++] = arr[i++]
            } else {
                temp[k++] = arr[j++]
            }
        }

        while (i <= mid) {
            temp[k++] = arr[i++]
        }
        while (j <= r) {
            temp[k++] = arr[j++]
        }

        i = l
        j = 0
        while (i <= r) {
            arr[i] = temp[j]
            i++
            j++
        }
    }

具体代码实现(java)

private static void mergeSort(int[] arr, int l, int r) {

        if(l>=r){
            return;
        }

        int mid=l+ ((r-l)>>1);

        mergeSort(arr,l,mid);
        mergeSort(arr,mid+1,r);

        int[] temp=new int[r-l+1];
        int i=l;
        int j=mid+1;
        int k=0;

        while (i<=mid && j<=r){
            if(arr[i] <= arr[j]){
                temp[k++]=arr[i++];
            }else {
                temp[k++]=arr[j++];
            }
        }

        while (i<=mid){
            temp[k++]=arr[i++];
        }
        while (j<=r){
            temp[k++]=arr[j++];
        }

        for(i=l,j=0;i<=r;i++,j++){
            arr[i]=temp[j];
        }
    }