• 欢迎访问 winrains 的个人网站!
  • 本网站主要从互联网整理和收集了与Java、网络安全、Linux等技术相关的文章,供学习和研究使用。如有侵权,请留言告知,谢谢!

七大排序算法介绍

算法 winrains 来源:ClericYi 9个月前 (02-29) 55次浏览

交换排序

冒泡排序

对应代码

void sort() {
    // 修剪枝叶的优化方法
    // 基于原理:
    // 每一趟完整的循环就对完成一个最大值或者最小值的放置
    // 那每一趟都可以删去枝叶,也就是最大值或者最小值的位置
    // i的大小也同样可以确定已经完成排序的数值的个数
    for (int i = 0; i < array.length; i++) {
        for (int j = 0; j < array.length - i - 1; j++) {
            if (array[j] > array[j + 1]) {
                swap(array[j], array[j+1]);
            }
        }
    }
}

原理及其实现方式

代码的效果正好和图片相反,其实冒泡排序作为最简单的排序方法之一,基于的是一个这样的概念:两两交换,比较双方数值大的放在高位,数值小的则放在低位。

而暴力双重循环,就是他的实现方式。每一次都将最大的一位数放到了最后一位,或者反之,将最小的数放到了第一位。

快速排序

对应代码

static void sort(int left, int right) {
    if (left < right) {
        // 通过split已经完成了左右分割,左边数一定小于中线,右边数一定大于中线
        int mid = split(left, right);
        // 对左右分区再以中线划分
        sort(mid+1, right);
        sort(left, mid-1);
    }
}

static int split(int left, int right) {
    // 以当前范围数组的第一个值作为中线
    int temp = array[left];
    while(left < right){
        // 右指针出现了一个数比中线小,则与中线进行交换
        while(left < right && temp < array[right]) right--;
        array[left] = array[right];
        // 左指针出现了一个数比中线大,则与中线进行交换
        while(left < right && temp > array[left]) left++;
        array[right] = array[left];
    }
    // 此时left == right,并无所谓是谁来进行交换
    array[left] = temp;
    return left;
}

原理及其实现方式

快速排序其实是冒泡排序的升级版,同样的基于两两交换,但是引入了分治的思想。通过使用中线,对需要排序的区间进行了重新的一个划分,而这内部剩下的性能还有一方面就是在于这个中线,因为数值的比较不再是全局,而是局部,从效率计算上来讲一般情况可降到O(nlogn),当然极端情况就可能退化回我们的冒泡排序。

极端例子:5 -> 4 -> 3 -> 2 -> 1

也就是一个已经完成排序的数组,再经过快速排序,想要将数组排序,就将会造成快排的退化。而解决方案就是不再以首个数据作为中线的基准。

插入排序

直接插入排序

对应代码

void sort() {
    // 修建枝叶的方法虽然可以用,但是效果微乎其微
    // 因为这只是根据数学方法推算,可以得知变量i=0时,是不需要工作的,也就删去的一小部分的工作
    for (int i = 1; i < array.length; i++) {
        int j = i;
        int temp = array[i];
        // 如果当前已完成排序数组中,下标数值大于当前数值
        // 就把这个数值往后进行移动
        while (j > 0 && temp < array[j - 1]) {
            array[j] = array[j - 1];
            j--;
        }
        if (j != i) array[j] = temp;
    }
}

原理及其实现方式

插入排序,顾名思义,就是把数字放到合适的位置。原理上讲就是将一个无须数组拆分成了两个部分,一块有序,一块无序。不断的删去无须队列中的数值,放到有序队列中,最后也就成为了有序队列。

第一趟排序:(5) -> 3 -> 4 -> 7 -> 2 
第二趟排序:(3 -> 5 )-> 4 -> 7 -> 2 
第三趟排序:(3 -> 4 -> 5 )-> 7 -> 2 
。。。。以此类推

希尔排序

对应代码

static void sort() {
    // gap也就相当于组别
    for (int gap = array.length >> 1; gap > 0; gap /= 2) {
        for (int i = gap; i < array.length; i++) {
            int j = i;
            while (j - gap >= 0 && array[j] < array[j - gap]) {
                swap(array[j], array[j - gap]);
                j -= gap;
            }
        }
    }
}

原理及其实现方法

先对代码做一个解释: (1)gap:也就是是我说的组别,分成两个部分 (2)array[j]:右半边需要交换的序列 (3)array[j - gap]:左半边交换的序列 (4)j -= gap:是为了保障最后一位被遗忘的数据被处理。

原序列:4 -> 3 -> 2 -> 5 -> 1
第一趟过程1:(2) -> 3 -> (4) -> 5 ->1
第一趟过程2:2 -> (3) -> 4 -> (5) ->1
第一趟过程3:(1) -> 3 ->(2)-> 5 ->(4)

选择排序

简单选择排序

对应代码

void sort() {
    // 修剪枝叶的优化方法
    // 基于原理:和冒泡排序完全一致。
    for (int i = 0; i < array.length; i++) {
        // 用于标示最小值下标
        int min = i;
        // 循环方式找到最小值
        for (int j = i+1; j < array.length ; j++) {
            if (array[j] < array[min]) min = j;
        }
        swap(array[min], array[i]);
    }
}

原理及其实现方式

和冒泡排序简单程度同级的排序,基于这样一个概念:每次找到在维护的数组内部最小个的值,并将它放到对应范围的第一位。

实现方案同样还是暴力的双重循环进行一个求解过程。

堆排序

对应代码

static void sort(){
    int len = arr.length;
    // 构建大顶堆
    for (int i = (arr.length - 1) / 2; i >= 0; i--)
        heapSort(i, arr.length - 1);
    for (int i = arr.length - 1; i > 0; i--) {
        // 交换0,最后号位,也就把最大值放到了最后
        swap(0, i);
        // len减1,保证了最后一位数并不会处理
        // 也就完成了倒数的大数的排序
        len--;
        heapSort(0, len);
    }
}
    
static void heapSort(int i, int len) {
    if (i > len) return;
    int maxIdx = i;
    int firPosition = i * 2 + 1;
    int secPosition = i * 2 + 2;
    // 左右大小比较,左边为大
    if (firPosition < len && arr[firPosition] > arr[maxIdx]) maxIdx = firPosition;
    if (secPosition < len && arr[secPosition] > arr[maxIdx]) maxIdx = secPosition;

    if (maxIdx != i) {
        swap(maxIdx, i);
        heapSort(maxIdx, len);
    }
}

原理及其实现方式

堆排序,其实你也可以理解为一种树形排序,虽然没有把这个数组转化成树,但是基于的原理就是一种树形的概念。

(1)大顶堆(数组升序):arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2]

(2)小顶堆:arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2]

总结出来就是树形,而遍历方式就是一种层次形遍历比较:

原序列:4 -> 3 -> 2 -> 5 -> 1
构建大顶堆,树形对应数组的一份: 
       4        2无子树       4                    5    maxId变化    5
    /     \     不处理。    /    \               /    \   处理4    /   \
   3       2     ===>     5        2   ===>    4      2   ===>   4     2 
  / \           处理3    / \           处理4  /  \               / \
 5   1                  3   1                3    1            3   1

我们发现一旦出现值的变化,那就需要对子树进行最初相应的改变,但为什么这一步只是说完成树的构建呢? 因为她并不会去比较,左右子树的大小,他唯一能保证的就是一个节点的值一定大于左右子树,并且确定下跟节点的值。所以引出了我们的第二步就是真正的排序。

构建完大顶堆后的序列:5 -> 4 -> 2 -> 3 -> 1
进行完交换后:
       5         交换         1    
    /     \     0和4号位    /    \        回到上述的树形建立
   4       2     ===>     4        2  ===>
  / \                    / \              只是去除了4号位 
 3   1                  3   5          

归并排序

对应代码

static void sort(int L, int R) {
    if(L == R) {
        return;
    }
    int mid = ((L + R) >> 1);
    // 不断的对数组直接进行对半的拆分
    // 递归调用回归顺序
    // 先把左半边全部合并,再把右半边全部合并
    // 两两数组合并
    sort(L, mid);
    sort(mid + 1, R);
    merge(L, mid, R);
}

static void merge(int L, int mid, int R) {
    int[] temp = new int[R - L + 1];
    int i = 0;
    int p1 = L;
    int p2 = mid + 1;
    // 比较左右两部分的元素,哪个小,把那个元素填入temp中
    while(p1 <= mid && p2 <= R) {
        temp[i++] = array[p1] < array[p2] ? array[p1++] : array[p2++];
    }
    // 上面的循环退出后,把剩余的元素依次填入到temp中
    while(p1 <= mid) {
        temp[i++] = array[p1++];
    }
    while(p2 <= R) {
        temp[i++] = array[p2++];
    }
    // 把最终的排序的结果复制给原数组
    for(i = 0; i < temp.length; i++) {
        array[L + i] = temp[i];
    }
}

原理及其实现方式

从图中已经知道了,归并排序和快排的思路正好相反,为什么这么说呢,快排在拆分的时候其实是拆分的时候通过中线分割,而归并是在是先把整个数组直接做一个对半拆分再对比合并。

拆分不是难事,但是合并真的很麻烦。如果只有两个数据比较,那么只用判断a > b,再来一个swap(a, b)。但是两个数组的比较呢?

原序列:4 -> 3 -> 2 -> 5 -> 1
左半边序列回归的时候需要进行的比较,经过推算肯定是第一次两个数组合并是:
4 -> 3的比较,这个时候具体merge(0, 0, 1);
归并的做法是创建一个新的数组空间来存放。
(1)两个数组 {[4], [3]},这里会将数组小的一个个塞进新数组temp中。
    while(p1 <= mid && p2 <= R) {
        temp[i++] = array[p1] < array[p2] ? array[p1++] : array[p2++];
    }

(2)而下方的自加策略是对未运算完的数据全部数据一股脑塞进temp中。
    仔细观察可以发现其实只完成了对数组[3]的赋值,就跳出了这一重循环。
    while(p1 <= mid) {
        temp[i++] = array[p1++];
    }
    while(p2 <= R) {
        temp[i++] = array[p2++];
    }

总结

因为算法的使用肯定考虑到使用场景,所以知道时空复杂度,是使用使用算法的前提。但是已经不再提倡选择和冒泡排序了,因为效率实在太差。

作者:ClericYi
来源:https://juejin.im/post/5e5247e4f265da57297889d5


版权声明:文末如注明作者和来源,则表示本文系转载,版权为原作者所有 | 本文如有侵权,请及时联系,承诺在收到消息后第一时间删除 | 如转载本文,请注明原文链接。
喜欢 (1)