Home 算法

0 19

堆排序(Heapsort)是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构,并同时满足堆积的性质:即子结点的键值或索引总是小于(或者大于)它的父节点。

7.1 算法描述

  • 将初始待排序关键字序列(R1,R2….Rn)构建成大顶堆,此堆为初始的无序区;
  • 将堆顶元素R[1]与最后一个元素R[n]交换,此时得到新的无序区(R1,R2,……Rn-1)和新的有序区(Rn),且满足R[1,2…n-1]<=R[n];
  • 由于交换后新的堆顶R[1]可能违反堆的性质,因此需要对当前无序区(R1,R2,……Rn-1)调整为新堆,然后再次将R[1]与无序区最后一个元素交换,得到新的无序区(R1,R2….Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1,则整个排序过程完成。

7.2 动图演示

 

https://blog.csdn.net/qq_28063811/article/details/93034625

0 21

5、归并排序(Merge Sort)

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为2-路归并。

5.1 算法描述

  • 把长度为n的输入序列分成两个长度为n/2的子序列;
  • 对这两个子序列分别采用归并排序;
  • 将两个排序好的子序列合并成一个最终的排序序列。

5.2 动图演示

 

import java.util.Arrays;
import java.util.Random;

/**
 * @Author Chengzhi
 * @Date 2021/9/5 10:03
 * @Version 1.0
 *
 * 归并排序
 */
public class MergeSort {

    public static void main(String[] args) {
        //生成随机数组
        Random rd = new Random();
        int[] num = new int[10];
        for (int i = 0; i < 10; i++) {
            num[i] = rd.nextInt(100) + 1;
        }
        System.out.println(Arrays.toString(num));
        //进行归并排序
        mergeSort(num, 0, num.length-1);
        System.out.println(Arrays.toString(num));
    }

    private static void mergeSort(int[] num, int left, int right) {
        if (left >= right) {//递归终止条件
            return;
        }
        int mid = (left + right) / 2;
        mergeSort(num, left, mid);//排序左序列
        mergeSort(num, mid + 1, right);//排序右序列
        merge(num, left, mid, right); //将左右两部分,利用临时数组进行归并
    }

    private static void merge(int[] arr, int left, int mid, int right) {
        int[] aux = new int[right - left + 1]; //临时辅助数组
        for (int i = left; i <= right; i++)
            aux[i - left] = arr[i]; /*减去的left是原数组相对于临时数组的偏移量*/

        int i = left, j = mid + 1;
        for (int k = left; k <= right; k++) {
            if (i > mid) { //检查左下标是否越界
                arr[k] = aux[j - left];
                j++;
            } else if (j > right) { //检查右下标是否越界
                arr[k] = aux[i - left];
                i++;
            } else if (aux[i - left] <= aux[j - left]) {
                arr[k] = aux[i - left];
                i++;
            } else {
                arr[k] = aux[j - left];
                j++;
            }
        }
    }
}

0 23

3、插入排序(Insertion Sort)

插入排序(Insertion-Sort)的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。

3.1 算法描述

一般来说,插入排序都采用in-place在数组上实现。具体算法描述如下:

  • 从第一个元素开始,该元素可以认为已经被排序;
  • 取出下一个元素,在已经排序的元素序列中从后向前扫描;
  • 如果该元素(已排序)大于新元素,将该元素移到下一位置;
  • 重复步骤3,直到找到已排序的元素小于或者等于新元素的位置;
  • 将新元素插入到该位置后;
  • 重复步骤2~5。

 

import java.util.Arrays;
import java.util.Random;

/**
 * @Author Chengzhi
 * @Date 2021/9/3 16:17
 * @Version 1.0
 *
 * 插入排序
 */
public class InsertionSort {

    public static void main(String[] args) {
        //生成随机数组
        Random rd = new Random();
        int[] num = new int[10];
        for (int i = 0; i < 10; i++) {
            num[i] = rd.nextInt(100) + 1;
        }
        System.out.println(Arrays.toString(num));
        //进行插入排序
        InsertSort(num);
        System.out.println(Arrays.toString(num));
    }
    private static int[] InsertSort(int[] num){
        //从第一个元素开始,该元素可以认为已经被排序;
        //取出下一个元素,在已经排序的元素序列中从后向前扫描;
        //如果该元素(已排序)大于新元素,将该元素移到下一位置;
        //重复步骤3,直到找到已排序的元素小于或者等于新元素的位置;
        //将新元素插入到该位置后;
        //重复步骤2~5。
        int len = num.length;
        int preIndex, current;
        for(int i = 1; i < len; i++) {
            preIndex = i - 1;//preIndex 为前一个元素
            current = num[i];//
            while(preIndex >= 0 && num[preIndex] > current) {//防止越界并且已排序序列元素大于新元素
                num[preIndex + 1] = num[preIndex];//已排序序列元素后移,为新元素腾位置
                preIndex--;
            }
            num[preIndex + 1] = current;
        }
        return num;
    }
}

0 18

2、选择排序(Selection Sort)

选择排序(Selection-sort)是一种简单直观的排序算法。它的工作原理:首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。以此类推,直到所有元素均排序完毕。

2.1 算法描述

n个记录的直接选择排序可经过n-1趟直接选择排序得到有序结果。具体算法描述如下:

  • 初始状态:无序区为R[1..n],有序区为空;
  • 第i趟排序(i=1,2,3…n-1)开始时,当前有序区和无序区分别为R[1..i-1]和R(i..n)。该趟排序从当前无序区中-选出关键字最小的记录 R[k],将它与无序区的第1个记录R交换,使R[1..i]和R[i+1..n)分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区;
  • n-1趟结束,数组有序化了。

2.2 动图演示

 

 

import java.util.Arrays;
import java.util.Random;

/**
 * @Author Chengzhi
 * @Date 2021/9/3 15:50
 * @Version 1.0
 *
 * 选择排序实现
 */
public class SelectionSort {

    public static void main(String[] args) {
        //生成随机数组
        Random rd = new Random();
        int[] num = new int[10];
        for (int i = 0; i < 10; i++) {
            num[i] = rd.nextInt(100) + 1;
        }
        System.out.println(Arrays.toString(num));
        //进行选择排序
        SelectionSort(num);
        System.out.println(Arrays.toString(num));
    }
    private static int[] SelectionSort(int[] num) {
        // 选择排序的工作原理:
        // 首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置
        // 然后,再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。
        // 以此类推,直到所有元素均排序完毕。 
        int i = 0;
        int j = 0;
        int min;
        int temp = 0;
        for(i = 0;i < num.length - 1;i++){//已排序序列下标;
            min = i;
            for(j = i + 1;j < num.length;j++){//找到最小的元素
                if(num[j] < num[min]){
                    min = j ;//记住下标即可;
                }
            }
            //交换
            temp = num[min];
            num[min] = num[i];
            num[i] = temp;
        }
        return num;
    }
}

0 96

0、算法概述

0.1 算法分类

十种常见排序算法可以分为两大类:

  • 比较类排序:通过比较来决定元素间的相对次序,由于其时间复杂度不能突破O(nlogn),因此也称为非线性时间比较类排序。
  • 非比较类排序:不通过比较来决定元素间的相对次序,它可以突破基于比较排序的时间下界,以线性时间运行,因此也称为线性时间非比较类排序。

0.2 算法复杂度

0.3 相关概念

  • 稳定:如果a原本在b前面,而a=b,排序之后a仍然在b的前面。
  • 不稳定:如果a原本在b的前面,而a=b,排序之后 a 可能会出现在 b 的后面。
  • 时间复杂度:对排序数据的总的操作次数。反映当n变化时,操作次数呈现什么规律。
  • 空间复杂度:是指算法在计算机

内执行时所需存储空间的度量,它也是数据规模n的函数。

 

冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列,一次比较两个元素,如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

1.1 算法描述

  • 比较相邻的元素。如果第一个比第二个大,就交换它们两个;
  • 对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对,这样在最后的元素应该会是最大的数
  • 针对所有的元素重复以上的步骤,除了最后一个;(此步骤优化了冒泡排序)
  • 重复步骤1~3,直到排序完成。

1.2 动图演示

注意内外层循环代表的含义不同!!!

代码如下:

package BubbleSort;

import java.util.Arrays;
import java.util.Random;

/**
 * @Author Chengzhi
 * @Date 2021/8/28 19:14
 * @Version 1.0
 *
 * 冒泡排序实现
 */
public class BubbleSort {

    public static void main(String[] args) {
        //生成随机数组
        Random rd = new Random();
        int[] num = new int[10];
        for (int i = 0; i < 10; i++) {
            num[i] = rd.nextInt(100) + 1;
        }
        System.out.println(Arrays.toString(num));
        //进行冒泡排序
        BubbleSort(num);
        System.out.println(Arrays.toString(num));
    }
    private static int[] BubbleSort(int[] num) {
        int i = 0;
        int j = 10;
        for(i = 0;i < 10 - 1;i++){//外层循环控制循环次数
            for(j = 0;j < 10 - 1 - i;j++){//内层循环控制两两对比
                if(num[j] > num[j + 1]){//前数比后数大,则交换
                    int temp = 0;
                    temp = num[j + 1];
                    num[j + 1] = num[j];
                    num[j] = temp;
                }
            }
        }
        return num;
    }
}

0 18

今天面武汉的一家公司被问到了快速排序的知识,特此记录,快排在排序算法中用的还蛮多的。

 

排序算法相关概念介绍:

0.1 算法分类

十种常见排序算法可以分为两大类:

  • 比较类排序:通过比较来决定元素间的相对次序,由于其时间复杂度不能突破O(nlogn),因此也称为非线性时间比较类排序。
  • 非比较类排序:不通过比较来决定元素间的相对次序,它可以突破基于比较排序的时间下界,以线性时间运行,因此也称为线性时间非比较类排序。

0.2 算法复杂度

0.3 相关概念

  • 稳定:如果a原本在b前面,而a=b,排序之后a仍然在b的前面。
  • 不稳定:如果a原本在b的前面,而a=b,排序之后 a 可能会出现在 b 的后面。
  • 时间复杂度:对排序数据的总的操作次数。反映当n变化时,操作次数呈现什么规律。
  • 空间复杂度:是指算法在计算机

内执行时所需存储空间的度量,它也是数据规模n的函数。

 

快速排序(Quick Sort)

概述:

快速排序是一种不稳定的比较排序算法

基本思想:

通过一趟排序将待排记录分隔成独立的两部分,其中一部分记录的关键字均比另一部分的关键字小,则可分别对这两部分记录继续进行排序,以达到整个序列有序。

快速排序是对冒泡排序算法的一种改进,同冒泡排序一样,快速排序也属于交换排序,通过元素之间的比较和交换位置来达到排序的目的。不同的是,冒泡排序在每一轮只把一个元素冒泡到数列的一端,而快速排序在每一轮挑选一个基准元素,并让其他比它大的元素移动到数列一边,比它小的元素移动到数列的另一边,从而把数列拆解成了两个部分,这种思路就叫做分治法
快速排序是基于“分治法”原理实现,所谓分治法就是不断的将原数组序列按照一定规律进行拆分,拆分后各自实现排序直到拆分到序列只剩下一个关键字为止。快速排序首先选取一个关键字为标志位(关键字的选取影响排序效率),然后将序列中小于标志位的关键字移动至标志位左侧,大于标志位的关键字移动至右侧。一趟比较完成后,整个序列以选取的标志位为界,左侧均小于标志位,右侧均大于关键字。但左右两侧内部并不是有序的(左右两侧关键字个数也不一定相同)。进而继续将左右两侧分别再以这种方式进行排序,直到将序列拆分的剩余一个关键字为止,整个序列即变成有序。

算法描述

快速排序使用分治法来把一个串(list)分为两个子串(sub-lists)。具体算法描述如下:

  • 从数列中挑出一个元素(一般挑第一个元素),称为 “基准”(pivot);
  • 重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。在这个分区退出之后,该基准就处于数列的中间位置。这个称为分区(partition)操作;
  • 递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序。

针对快速排序我的理解始终有些模糊,因此本次我决定编写快排代码并一步步调试,弄懂其原理:(偷懒转自知乎)

1.首先,随机生成十个数字

作者:汇智知了堂
链接:https://zhuanlan.zhihu.com/p/363421644
来源:知乎
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

 Random rd = new Random();
        int[] num = new int[10];
        for (int i = 0; i < num.length; i++) {
            num[i] = rd.nextInt(100)+1;
        }
        System.out.println(Arrays.toString(num));

所得如下:

我们便以这十个数字进行对快速排序思想的说明。

我们需要选定基准数,这里,我们选择第一个数字为基准数,即15。

我们用L存储第一个元素的下标,用R存储最后一个元素的下标,如图所示:

我们从R开始往前找,找第一个小于val的数字,放到L的位置,L++。

我们发现,8小于val,则变动如下图所示:

然后我们从L开始往后找,找到第一个大于val的数字,放到R的位置,R- -。

我们发现,46大于val,则变动如下图所示:

2、之后循环这两步,直到L与R相等,我们将基准数放在他们为下标的位置

即如下图所示:

这样,我们就将小于基准数的数字全部放在了基准数的左边,大于基准数的全部放在了基准数的右边。

我们将基准数的左边的数字和基准数右边的数字分别进行上述所有步骤如下图,直至一个分支只有一个元素。

作者:汇智知了堂
链接:https://zhuanlan.zhihu.com/p/363421644
来源:知乎
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

3、后面的步骤就是前面步骤的重复,我就不一一描述

直接给出最后的图如下:

4、排序结果为:8 15 36 46 51 55 82 86 89 96

快排代码如下所示,仅供参考:

public class testSort {
    public static void main(String[] args) {
        Random rd = new Random();
        int[] num = new int[10];
        for (int i = 0; i < num.length; i++) {
            num[i] = rd.nextInt(100)+1;
        }
        System.out.println(Arrays.toString(num));
        quickSort(num,0,num.length-1);
        System.out.println(Arrays.toString(num));
    }
    /**
     * 实现快速排序
     * @param num
     * @param i
     * @param j
     */
    public static void quickSort(int[] num,int i,int j){
        if(i >= j){//只剩一个元素不用处理直接结束。
            return;
        }
        //选取基准数
        int val =num[i];
        int l = i;
        int r = j;
        while(l < r){//当l == r时,就是调整完成时
            //从后往前找第一个小于val的数字
            while (l < r && num[r] > val){
                r --;
            }
            if(l < r){//找到了数字
                num[l++] = num[r];
            }
            //从前往后找第一个大于val的数字
            while (l < r && num[l] < val){
                l ++;
            }
            if(l < r){//找到了数字
                num[r--] = num[l];
            }
        }
        //l==r,基准数放进去
        num[l] = val;
        quickSort(num,i,l-1);
        quickSort(num,l+1,j);
    }
}

5、运行结果如下: