十大经典排序与总结

发布于 2020-11-18  144 次阅读


今天的每日一题写过了,因此就来总结一下十大排序算法。

在这里更新一个非常牛逼的视频(来源b站,侵删),可视化了主流的排序,非常棒!

冒泡排序

冒泡排序大概是接触最早的一种排序了。这种排序非常直观,排序时遍历未排序的所有项,每次比较相邻的两个,并把比较后的两数按照要求排列(如小的放在前面或者大的放在前面等)。

冒泡排序可以进行改进,比方说设立一个flag值,若是遍历全部未排序的数都没有发生交换,则可以认为排序已经完成,可以提前break。

显然,冒泡排序的时间复杂度为n^2,空间复杂度为1.

代码实现:

public class BubbleSort implements IArraySort {

    @Override
    public int[] sort(int[] sourceArray) throws Exception {
        // 对 arr 进行拷贝,不改变参数内容
        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);

        for (int i = 1; i < arr.length; i++) {
            // 设定一个标记,若为true,则表示此次循环没有进行交换,也就是待排序列已经有序,排序已经完成。
            boolean flag = true;

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

                    flag = false;
                }
            }

            if (flag) {
                break;
            }
        }
        return arr;
    }
}

选择排序

选择排序其实也差不多,只是比冒泡排序少了每次都交换位置。

在选择排序中,我们每次遍历一遍所有未排序的地方,一直比较,最终把min(或者是max)放到数组的最前方。

该方法的时间复杂度也是n的平方。

代码实现:

public class SelectionSort implements IArraySort {

    @Override
    public int[] sort(int[] sourceArray) throws Exception {
        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);

        // 总共要经过 N-1 轮比较
        for (int i = 0; i < arr.length - 1; i++) {
            int min = i;

            // 每轮需要比较的次数 N-i
            for (int j = i + 1; j < arr.length-1; j++) {
                if (arr[j] < arr[min]) {
                    // 记录目前能找到的最小值元素的下标
                    min = j;
                }
            }

            // 将找到的最小值和i位置所在的值进行交换
            if (i != min) {
                int tmp = arr[i];
                arr[i] = arr[min];
                arr[min] = tmp;
            }

        }
        return arr;
    }
}

插入排序

插入排序也挺简单粗暴的。

算法过程如下:

将第一个位置视为有序序列,将第二个位置到最后一个位置视为未排序序列。

依次遍历未排序序列,每次选取第一个元素,与有序数列中的数进行比较,插入到其应该插入的位置中去。

插入排序最好情况的时间复杂度为O(n)

代码实现:

public class InsertSort implements IArraySort {

    @Override
    public int[] sort(int[] sourceArray) throws Exception {
        // 对 arr 进行拷贝,不改变参数内容
        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);

        // 从下标为1的元素开始选择合适的位置插入,因为下标为0的只有一个元素,默认是有序的
        for (int i = 1; i < arr.length; i++) {

            // 记录要插入的数据
            int tmp = arr[i];

            // 从已经排序的序列最右边的开始比较,找到比其小的数
            int j = i;
            while (j > 0 && tmp < arr[j - 1]) {
                arr[j] = arr[j - 1];
                j--;
            }

            // 存在比其小的数,插入
            if (j != i) {
                arr[j] = tmp;
            }

        }
        return arr;
    }
}

希尔排序

希尔排序是一种改进版的插入排序。其利用了插入排序的特点:

一、插入排序在序列接近于排序完成时效率比较高,可以达到线性的速度

二、因为每次只能移动一位,插入排序在大部分时候都是比较低效的

为了解决上述的问题,我们设置一个步长序列S。每次步长取Si(i=1,2.....n),其中Sn=1.

需要注意的是,因为一开始步长比较大的缘故,可能不能可能只能包括一两组同余的数,并进行排序。

每次都是相隔为步长的元素之间进行比较。比如说步长为4的时候就是第2个元素与第6个元素进行比较。

我们把下标同余某数的,属于同一个步长的节点集合看成一个序列,在这个序列中使用插入排序,这样解决了每次只能移动一个距离的问题。

同时,当快要排序完成时,最后一次,我们选择步长为1,也就是整个序列,进行插入排序。这样在快要完成排序时,插入排序效率较高。

代码实现:

public class ShellSort implements IArraySort {

    @Override
    public int[] sort(int[] sourceArray) throws Exception {
        // 对 arr 进行拷贝,不改变参数内容
        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);

        int gap = 1;
        while (gap < arr.length/3) {
            gap = gap * 3 + 1;
        }

        while (gap > 0) {
            for (int i = gap; i < arr.length; i++) {
                int tmp = arr[i];
                int j = i - gap;
                while (j >= 0 && arr[j] > tmp) {
                    arr[j + gap] = arr[j];
                    j -= gap;
                }
                arr[j + gap] = tmp;
            }
            gap = (int) Math.floor(gap / 3);
        }

        return arr;
    }
}

归并排序

归并排序(Merge sort)是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。

作为一个典型的分治算法,归并排序可以使用自顶向下的递归实现,又或者是自底向上的迭代实现。

归并排序的算法步骤如下:

1.申请空间,空间大小为两个已经排序好的空间的大小之和

2.将两指针分别指向已经排序好的空间,比较大小,将小(大)的放入申请的空间中,并将指向放入数据的指针指向下一个位置。

3.重复第二步直到其中某一指针指向末尾。将另一个指针所指空间后面剩余的元素合并上来。

4.递归上述过程,直到结束排序。

归并排序的时间复杂度是O(nlogn).原因如下图。

算法实现的动图示意图如下:

代码实现:

public class MergeSort implements IArraySort {

    @Override
    public int[] sort(int[] sourceArray) throws Exception {
        // 对 arr 进行拷贝,不改变参数内容
        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);

        if (arr.length < 2) {
            return arr;
        }
        int middle = (int) Math.floor(arr.length / 2);

        int[] left = Arrays.copyOfRange(arr, 0, middle);
        int[] right = Arrays.copyOfRange(arr, middle, arr.length);

        return merge(sort(left), sort(right));
    }

    protected int[] merge(int[] left, int[] right) {
        int[] result = new int[left.length + right.length];
        int i = 0;
        while (left.length > 0 && right.length > 0) {
            if (left[0] <= right[0]) {
                result[i++] = left[0];
                left = Arrays.copyOfRange(left, 1, left.length);
            } else {
                result[i++] = right[0];
                right = Arrays.copyOfRange(right, 1, right.length);
            }
        }

        while (left.length > 0) {
            result[i++] = left[0];
            left = Arrays.copyOfRange(left, 1, left.length);
        }

        while (right.length > 0) {
            result[i++] = right[0];
            right = Arrays.copyOfRange(right, 1, right.length);
        }

        return result;
    }

}

快排

快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下,排序 n 个项目要 Ο(nlogn) 次比较。在最坏状况下则需要 Ο(n^2) 次比较,但这种状况并不常见。事实上,快速排序通常明显比其他 Ο(nlogn) 算法更快,因为它的内部循环(inner loop)可以在大部分的架构上很有效率地被实现出来。

快速排序使用分治法(Divide and conquer)策略来把一个串行(list)分为两个子串行(sub-lists)。

快速排序又是一种分而治之思想在排序算法上的典型应用。本质上来看,快速排序应该算是在冒泡排序基础上的递归分治法。

虽然快排在 worst case的情况下时间复杂度会变成O(n^2),但是在一般情况下,因为大部分的数据都是较为无序的,而且快排log下的常数因子较小,因此比复杂度同样为nlogn的归并排序要快上许多。

算法步骤:

1.选取一个值,作为基准值“pivot”。

2.将小于基准值的放入左边,大于基准值的放到右边。本轮递归结束的时候基准值应该左右两边被分为了“比基准值小”和“比基准值大”两个区域。

3.递归地对分区进行上述操作,直到分区长度为0或者为1,结束递归。

代码实现:

空间复杂度为O(n)伪代码:

 function quicksort(q)
 {
     var list less, pivotList, greater
     if length(q) ≤ 1 
         return q
     else 
     {
         select a pivot value pivot from q
         for each x in q except the pivot element
         {
             if x < pivot then add x to less
             if x ≥ pivot then add x to greater
         }
         add pivot to pivotList
         return concatenate(quicksort(less), pivotList, quicksort(greater))
     }
 }

in-place(即空间复杂度为O(1))的实现:

原地分割的伪代码如下:
 function partition(a, left, right, pivotIndex)
 {
     pivotValue = a[pivotIndex]
     swap(a[pivotIndex], a[right]) // 把pivot移到結尾
     storeIndex = left
     for i from left to right-1
     {
         if a[i] <= pivotValue
          {
             swap(a[storeIndex], a[i])
             storeIndex = storeIndex + 1
          }
     }
     swap(a[right], a[storeIndex]) // 把pivot移到它最後的地方
     return storeIndex
 }

这是原地分割算法,它分割了标示为"左边(left)"和"右边(right)"的序列部分,借由移动小于a[pivotIndex]的所有元素到子序列的开头,留下所有大于或等于的元素接在他们后面。在这个过程它也为基准元素找寻最后摆放的位置,也就是它回传的值。它暂时地把基准元素移到子序列的结尾,而不会被前述方式影响到。由于算法只使用交换,因此最后的数列与原先的数列拥有一样的元素。要注意的是,一个元素在到达它的最后位置前,可能会被交换很多次。

网上代码:
public class QuickSort implements IArraySort {

    @Override
    public int[] sort(int[] sourceArray) throws Exception {
        // 对 arr 进行拷贝,不改变参数内容
        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);

        return quickSort(arr, 0, arr.length - 1);
    }

    private int[] quickSort(int[] arr, int left, int right) {
        if (left < right) {
            int partitionIndex = partition(arr, left, right);
            quickSort(arr, left, partitionIndex - 1);
            quickSort(arr, partitionIndex + 1, right);
        }
        return arr;
    }

    private int partition(int[] arr, int left, int right) {
        // 设定基准值(pivot)
        int pivot = left;
        int index = pivot + 1;
        for (int i = index; i <= right; i++) {
            if (arr[i] < arr[pivot]) {
                swap(arr, i, index);
                index++;
            }
        }
        swap(arr, pivot, index - 1);
        return index - 1;
    }

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

}
我自己实现的代码:

区别主要在原地排序的实现方面。

    public int[] quickSort(int[] sourceArray,int left,int right){
//        int[] arr = Arrays.copyOf(sourceArray,sourceArray.length);
        if(left<right){
            int partitionIndex = partition(sourceArray,left,right);
            quickSort(sourceArray,left,partitionIndex-1);
            quickSort(sourceArray,partitionIndex+1,right);
        }
        return sourceArray;
    }

    private int partition(int[] arr, int left, int right) {
//        选取left作为基准
//        int pivotValue = arr[(int)Math.floor((left+right)/2)];
        int pivotValue = arr[left];
//        swap(arr,left,right);
        int pivotLocation = left;
        swap(arr,pivotLocation,right);
        for (int i = left; i <= right-1; i++) {
            if (arr[i]<=pivotValue){
                swap(arr,pivotLocation,i);
                pivotLocation+=1;
            }
        }
        swap(arr,pivotLocation,right);
        return pivotLocation;
    }

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

堆排序

堆排序利用的是堆(heap)这个数据结构的特性--根节点的值总是大(小)于子节点,且左右子树依然为堆。

补充知识--堆的建立与删除

堆的删除

当我们要移除堆顶端的点时,为了保证数据结构的完整性(依然是完全二叉树),我们可以交换堆的根节点和(完全二叉树中)最末尾的节点,并将heap.size-1.

接下来我们的任务就是保证堆的另一个性质--根节点大(小)于左右孩子的值。

这时,我们应该考虑到,我们只是交换了根节点和完全二叉树最后一个节点的位置。那么根节点的左右子树依然是堆,因此我们只需要在左右孩子中选择一个较大的与当前根节点交换位置,并在交换后继续上面的步骤,直到找到刚刚在根节点位置的值新的位置即可。

堆的建立

我们在堆的删除中,利用了左右子树都是堆这个性质,那么在堆建立时,也可以使用这个性质。

但是这时候我们只能自底向上实现。

选取最后一个有孩子的节点,将其变为堆,再到倒数第二个有孩子的节点(也就是图中的30)将其变为堆。变堆的过程也就是比较左右孩子和节点本身,选取较大的作为当前子树的根节点。

依次自底向上找当前子树的根节点即可。

代码实现:

    private int[] heapSort(int[] arr){
        /*
         *  第一步:将数组堆化
                *  beginIndex = 第一个非叶子节点。
         *  从第一个非叶子节点开始即可。无需从最后一个叶子节点开始。
         *  叶子节点可以看作已符合堆要求的节点,根节点就是它自己且自己以下值为最大。
         */
        int maxIndex = arr.length-1;
        int beginIndex =(int) Math.floor(maxIndex/2);
        for (int i = beginIndex; i >=0 ; i--) {
            maxHeapifty(arr,i,maxIndex);
        }
        /*
         * 第二步:对堆化数据排序
         * 每次都是移出最顶层的根节点A[0],与最尾部节点位置调换,同时遍历长度 - 1。
         * 然后从新整理被换到根节点的末尾元素,使其符合堆的特性。
         * 直至未排序的堆长度为 0。
         */
        for (int i = maxIndex; i >0 ; i--) {
            swap(arr,0,i);
            maxHeapifty(arr,0,i-1);
        }
        return arr;


    }

    private  void maxHeapifty(int[] arr,int index,int length){
        int leftChild = index*2+1;
        int rightChild = leftChild+1;
        if(leftChild>length){
            return;
        }
        int currentIndex;
        if (rightChild<=length) {
            currentIndex = arr[leftChild]>arr[rightChild]?leftChild:rightChild;
        }
        else {
            currentIndex = leftChild;
        }
        if(arr[currentIndex]>arr[index]){
            swap(arr,currentIndex,index);
            maxHeapifty(arr,currentIndex,length);
        }
    }

    private void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;

    }

计数排序

计数排序就是利用额外开辟的空间,按照顺序(比如从小到大)存储每个数字出现的频率,并依次把结果存入res数组中。该排序方式的时间复杂度是线性的。但是这个排序方法要求知道目标数组的范围。

代码实现:

private int[] countSort(int[] arr){
//        int min = findMin(arr);
//        int max = findMax(arr);
        int range = findMax(arr)  + 1;
        int[] countArray = new int[range];
        for (int a:
            arr) {
            countArray[a]++;
        }
        int sortIndex = 0;
        for (int i = 0; i < range; i++) {
            while(countArray[i]>0){
                arr[sortIndex++]=i;
                countArray[i]--;
            }
        }
        return arr;
    }

    private int findMax(int[] arr){
        int maxValue=Integer.MIN_VALUE;
        for (int a:
             arr) {
            maxValue = Math.max(maxValue,a);
        }
        return maxValue;
    }

    private int findMin(int[] arr){
        int minValue=Integer.MAX_VALUE;
        for (int a:
                arr) {
            minValue = Math.min(minValue,a);
        }
        return minValue;
    }

上面的方法(从0开始)会造成暂存顺序的数组过大,下面一个是改进后的方法(以最小值为基准,寻找暂存数组中的数)。

	public static int[] countSort(int []a){
		int b[] = new int[a.length];
		int max = a[0], min = a[0];
		for(int i : a){
			if(i > max){
				max = i;
			}
			if(i < min){
				min = i;
			}
		}
		//这里k的大小是要排序的数组中,元素大小的极值差+1
		int k = max - min + 1;
		int c[] = new int[k];
		for(int i = 0; i < a.length; ++i){
			c[a[i]-min] += 1;//优化过的地方,减小了数组c的大小
		}
		for(int i = 1; i < c.length; ++i){
			c[i] = c[i] + c[i-1];
		}
		for(int i = a.length-1; i >= 0; --i){
			b[--c[a[i]-min]] = a[i];//按存取的方式取出c的元素
		}
		return b;
	}

桶排序

桶排序就是把目标分成一个一个的子区间(桶),然后分别对每个桶进行排序。

具体算法如下:

1.扫描得到数的范围(min,max),设桶的个数为k,把区间均匀地分为k个子区间,并把值在对应范围内的成员放入子区间中。

2.选取排序方法(比如说快排)对每个子区间进行排序。

3.合并所有子区间。

复杂度分析

如果使用快排对子区间进行排序,则子区间的时间复杂度为O((n/k)*log(n/k))。所有区间的复杂度则为O(n*log(n/k))也就是O(nlogn-nlogk),当分区数k越接近n时,时间复杂度越接近于O(n)线性复杂度。

什么情况下桶排序比较快?

如果能够均匀地把桶放在不同的桶中则比较快,若所有数都在一个桶中则比较慢,同时,如果数比较稀疏,桶的size又比较小,则会出现很多空桶,造成对空间的浪费。

代码实现:

    private int[] bucketSort(int[]arr,int bucketSize){
        if(arr.length==0) {
            return arr;
        }
        int minValue = findMin(arr);
        int maxValue = findMax(arr);
        int bucketCount = (int) Math.floor((maxValue - minValue) / bucketSize) + 1;
        int[][] bucket = new int[bucketCount][0];
        for (int j : arr) {
            int index = (int) Math.floor((j - minValue) / bucketSize);
            bucket[index] = arrAppend(bucket[index], j);
        }
        int sortIndex = 0,bucketIndex=0;
        for (int[]a:
             bucket) {
            if(a.length<=0) {
                continue;
            }
            test.quickSort(a,bucketIndex,bucketIndex+a.length-1);
            for (int value:
                 a) {
                arr[sortIndex++]=value;
            }
        }
        return arr;
    }

基数排序:

基数排序就是按照某一基数把mod基数同余的数放入一个桶中,并且每次只比较一位。当基数为10的时候就是十进制的按位排序。

代码实现:

/**
 * 基数排序
 * 考虑负数的情况还可以参考: https://code.i-harness.com/zh-CN/q/e98fa9
 */
public class RadixSort implements IArraySort {

    @Override
    public int[] sort(int[] sourceArray) throws Exception {
        // 对 arr 进行拷贝,不改变参数内容
        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);

        int maxDigit = getMaxDigit(arr);
        return radixSort(arr, maxDigit);
    }

    /**
     * 获取最高位数
     */
    private int getMaxDigit(int[] arr) {
        int maxValue = getMaxValue(arr);
        return getNumLenght(maxValue);
    }

    private int getMaxValue(int[] arr) {
        int maxValue = arr[0];
        for (int value : arr) {
            if (maxValue < value) {
                maxValue = value;
            }
        }
        return maxValue;
    }

    protected int getNumLenght(long num) {
        if (num == 0) {
            return 1;
        }
        int lenght = 0;
        for (long temp = num; temp != 0; temp /= 10) {
            lenght++;
        }
        return lenght;
    }

    private int[] radixSort(int[] arr, int maxDigit) {
        int mod = 10;
        int dev = 1;
//最外层的循环就是代表位数的循环
        for (int i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) {
            // 考虑负数的情况,这里扩展一倍队列数,其中 [0-9]对应负数,[10-19]对应正数 (bucket + 10)
            int[][] counter = new int[mod * 2][0];
//这层循环把所有的数放到对应的桶里面去
            for (int j = 0; j < arr.length; j++) {
                int bucket = ((arr[j] % mod) / dev) + mod;
                counter[bucket] = arrayAppend(counter[bucket], arr[j]);
            }
// 对每个桶中的数按顺序取出
            int pos = 0;
            for (int[] bucket : counter) {
                for (int value : bucket) {
                    arr[pos++] = value;
                }
            }
        }

        return arr;
    }

    /**
     * 自动扩容,并保存数据
     *
     * @param arr
     * @param value
     */
    private int[] arrayAppend(int[] arr, int value) {
        arr = Arrays.copyOf(arr, arr.length + 1);
        arr[arr.length - 1] = value;
        return arr;
    }
}

终于,咕咕咕了一万年的排序文章终于写完了。


你好哇!欢迎来到雷公马碎碎念的地方:)