精华内容
下载资源
问答
  • 初学Java者,想要把Java基础学好,冒泡排序和快速排序是两个 必需学会并写会的算法。
  • Java快速排序(简单版)

    千次阅读 多人点赞 2020-03-01 11:52:34
    以下是通俗易懂的快速排序!摘自《啊哈!算法》,我将书中的C语言写成了Java语言。因为我觉得它真的很容易明白,所以我并将把他记录了下来,并分享给大家! 假设我们现在对“6 1 2 7 9 3 4 5 1 0 8”这10个数进行...

    以下是通俗易懂的快速排序!摘自《啊哈!算法》,我将书中的C语言写成了Java语言。因为我觉得它真的很容易明白,所以我并将把他记录了下来,并分享给大家!


    假设我们现在对“6 1 2 7 9 3 4 5 1 0 8”这10个数进行排序。首先在这个序列中随便找一个数作为基准数(不要被这个名词吓到了,这就是一个用来参照的数,待会儿你就知道它用来做啥了)。为了方便,就让第一个数6作为基准数吧。接下来,需要将这个序列中所有比基准数大的数放在6的右边,比基准数小的数放在6的左边,类似下面这种排列。

    3 1 2 5 4 6 9 7 1 0 8

    在初始状态下,数字6在序列的第1位。我们的目标是将6挪到序列中间的某个位置,假设这个位置是k。现在就需要寻找这个k,并且以第k位为分界点,左边的数都小于等于6,右边的数都大于等于6。想一想,你有办法可以做到这点吗?

    给你一个提示吧。请回忆一下冒泡排序是如何通过“交换”一步步让每个数归位的。此
    时你也可以通过“交换”的方法来达到目的。冒泡排序很浪费时间,每次都只能对相邻的两个数进行比较,这显然太不合理了。于是“快速排序”就要比冒泡排序要更快。


    分析如下:

    方法其实很简单:分别从初始序列“6 1 2 7 9 3 4 5 1 0 8”两端开始“探测”。先从右往左找一个小于6的数,再从左往右找一个大于6的数,然后交换它们。这里可以用两个变量i和j,分别指向序列最左边和最右边。我们为这两个变量起个好听的名字“哨兵i”和“哨兵j”。刚开始的时候让哨兵i指向序列的最左边(即i=1),指向数字6。让哨兵j指向序列的最右边(即j=10),指向数字8。
    在这里插入图片描述
    首先哨兵j开始出动。因为此处设置的基准数是最左边的数,所以需要让哨兵j先出动,这一点非常重要(自己想一想为什么)。哨兵j一步一步地向左挪动(即j–),直到找到个小于6的数停下来。接下来哨兵i再一步一步向右挪动(即i++),直到找到一个大于6的数停下来。最后哨兵j停在了数字5面前,哨兵i停在了数字7面前。
    在这里插入图片描述
    现在交换哨兵 i 和哨兵 j 所指向的元素的值。交换之后的序列如下。
    6 1 2 5 9 3 4 7 10 8

    到此,第一次交换结束。接下来哨兵 j 继续向左挪动(再次友情提醒,每次必须是哨兵
    j 先出发)。他发现了 4(比基准数 6 要小,满足要求)之后停了下来。哨兵 i 也继续向右挪
    动,他发现了 9(比基准数 6 要大,满足要求)之后停了下来。此时再次进行交换,交换之
    后的序列如下。
    3 1 2 5 4 6 9 7 10 8

    在这里插入图片描述
    到此第一轮“探测”真正结束。此时以基准数 6 为分界点,6 左边的数都小于等于 6,6
    右边的数都大于等于 6。回顾一下刚才的过程,其实哨兵 j 的使命就是要找小于基准数的数,
    而哨兵 i 的使命就是要找大于基准数的数,直到 i 和 j 碰头为止。

    OK,解释完毕。现在基准数 6 已经归位,它正好处在序列的第 6 位。此时我们已经将
    原来的序列,以 6 为分界点拆分成了两个序列,左边的序列是“3 1 2 5 4”,右边的序列是“9 7 10 8”。接下来还需要分别处理这两个序列,因为 6 左边和右边的序列目前都还是很混
    乱的。不过不要紧,我们已经掌握了方法,接下来只要模拟刚才的方法分别处理 6 左边和右
    边的序列即可。现在先来处理 6 左边的序列吧。左边的序列是“3 1 2 5 4”。也是照猫画虎同样的做法!调整完毕之后的序列的顺序应该是:
    2 1 3 5 4

    OK,现在 3 已经归位。接下来需要处理 3 左边的序列“2 1”和右边的序列“5 4”。对
    序列“2 1”以 2 为基准数进行调整,处理完毕之后的序列为“1 2”,到此 2 已经归位。序列
    “1”只有一个数,也不需要进行任何处理。至此我们对序列“2 1”已全部处理完毕,得到
    的序列是“1 2”。序列“5 4”的处理也仿照此方法,最后得到的序列如下。
    1 2 3 4 5 6 9 7 10 8

    对于序列“9 7 10 8”也模拟刚才的过程,直到不可拆分出新的子序列为止。最终将会
    得到这样的序列:
    1 2 3 4 5 6 7 8 9 10

    到此,排序完全结束。细心的同学可能已经发现,快速排序的每一轮处理其实就是将这
    一轮的基准数归位,直到所有的数都归位为止,排序就结束了。下面上个霸气的图来描述下
    整个算法的处理过程。
    在这里插入图片描述
    快速排序之所以比较快,是因为相比冒泡排序,每次交换是跳跃式的。每次排序的时候设置一个基准点,将小于等于基准点的数全部放到基准点的左边,将大于等于基准点的数全部放到基准点的右边。这样在每次交换的时候就不会像冒泡排序一样只能在相邻的数之间进行交换,交换的距离就大得多了。因此总的比较和交换次数就少了,速度自然就提高了。当然在最坏的情况下,仍可能是相邻的两个数进行了交换。因此快速排序的最差时间复杂度和冒泡排序是一样的,都是 O(N2),它的平均时间复杂度为 O (NlogN)。其实快速排序是基于一种叫做“二分”的思想。我们后面还会遇到“二分”思想,到时候再聊。先上代码,如下。

    /** 
    * @author Ziph
    * @date 2020年3月1日
    * @Email mylifes1110@163.com
    * 
    * 快速排序
    */
    public class TestQuickSort {
    	public static void main(String[] args) {
    		//创建一个数组并给每个数组元素赋值
    		int[] a = new int[] {19, 23, 5, 7, 16, 0, 10};
    		//调用快排方法
    		quickSort(a, 0, a.length - 1);
    		//打印输出排好序的数组元素
    		for (int i = 0; i < a.length; i++) {
    			System.out.print(a[i] + " ");
    		}
    	}
    	
    	public static void quickSort(int[] a,int left,int right){
    		//分别创建i哨兵、j哨兵、temp存储基准数的临时变量、t交换的临时变量
    		int i,j,temp,t;
    		
    		//终止递归,终止排序的条件(此时已经是排好的顺序)
    		if (left > right) {
    			return;
    		}
    		
    		//分别用i、j存储两个哨兵
    		i = left;
    		j = right;
    		//temp存储的就是基准数
    		temp = a[left];
    		
    		//跳出while循环之后,因为循环的条件是i<j,所以,跳出循环时,i和j是相等的
    		while (i < j) {
    			//哨兵j从右往左找
    			while (temp <= a[j] && i < j) {
    				j--;
    			}
    			//哨兵i从左往右找
    			while (temp >= a[i] && i < j) {
    				i++;
    			}
    			//交换两个数在数组中的位置
    			if (i < j) {//当哨兵i和哨兵j没有相遇时
    				t = a[j];
    				a[j] = a[i];
    				a[i] = t;
    			}
    		}
    		//最终基准数归位
    		a[left] = a[i];
    		a[i] = temp;
    		
    		quickSort(a, left, j - 1);//继续处理左边的,这里是递归的过程
    		quickSort(a, j + 1, right);//继续处理右边的,这里是递归的过程
    	}
    }
    

    执行结果:

    0 5 7 10 16 19 23 
    
    展开全文
  • Java实现快速排序

    万次阅读 多人点赞 2019-07-20 21:48:33
    给定一组数据,使用快速排序得到这组数据的非降序排列。 2 解决方案 2.1 快速排序原理简介 引用自百度百科: 快速排序(Quicksort)是对冒泡排序的一种改进。 快速排序由C. A. R. Hoare在1962年提出。它的基本思想是...

    1 问题描述
    给定一组数据,使用快速排序得到这组数据的非降序排列。

    2 解决方案
    2.1 快速排序原理简介
    引用自百度百科:

    快速排序(Quicksort)是对冒泡排序的一种改进。

    快速排序由C. A. R. Hoare在1962年提出。它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。

    具体排序过程:

    设要排序的数组是A[0]……A[N-1],首先任意选取一个数据(通常选用数组的第一个数)作为关键数据,然后将所有比它小的数都放到它前面,所有比它大的数都放到它后面,这个过程称为一趟快速排序。值得注意的是,快速排序不是一种稳定的排序算法,也就是说,多个相同的值的相对位置也许会在算法结束时产生变动。

    一趟快速排序的算法是:

    1)设置两个变量i、j,排序开始的时候:i=0,j=N-1(PS:即i从数组前开始向后遍历,j从数组后开始向前遍历);

    2)以第一个数组元素作为关键数据,赋值给key,即key=A[0];

    3)从j开始向前搜索,即由后开始向前搜索(j–),找到第一个小于key的值A[j],将A[j]和A[i]互换;

    4)从i开始向后搜索,即由前开始向后搜索(i++),找到第一个大于key的A[i],将A[i]和A[j]互换;(PS:3)和4)步核心思想就是i向后遍历遇到大于A[0]的元素,停下来等待;j向前遍历遇到小于A[0]的元素,停下来等待;然后交换此时的A[i]和A[j]的值;交换完后,i依旧自增遍历,j依旧自减遍历)

    5)重复第3、4步,直到i=j; (3,4步中,没找到符合条件的值,即3中A[j]不小于key,4中A[i]不大于key的时候改变j、i的值,使得j=j-1,i=i+1,直至找到为止。找到符合条件的值,进行交换的时候i, j指针位置不变。另外,i==j这一过程一定正好是i+或j-完成的时候,此时令循环结束)。

    下面来看一个具体排序示例:

    给定一组数据:5,3,1,9,8,2,4,7存入数组中

    在这里插入图片描述

    快速排序性能分析:

    在这里插入图片描述

    package com.liuzhen.chapterFive;
    
    public class Quicksort {
        /*
         * 该函数功能使用快速排序返回数组A的非降序序列
         * 输入数组A[0..n],其子数组为A[start..end]
         */
        public static void getQuicksort(int[] A,int start,int end){
            if(start < end){
                int s = HoarePartition(A,start,end);   //s是分裂位置,即排序结果序列的最终位置
                getQuicksort(A,start,(s-1));
                getQuicksort(A,(s+1),end);
            }
        }
        
        /*
         * 以数组第一个元素为中轴,对子数组进行划分
         * 返回分裂点在数组排序结果中的最终位置
         */
        public static int HoarePartition(int[] A,int start,int end){
            int p = A[start];
            int i = start+1;
            int j = end;
            if(i == j){
                if(A[j] >= p)   //此时分裂点右方只有一个元素,且大于分裂点处值
                    return start;
            }
            while(i < j){
                while(A[i] < p){
                    if(i == end)
                        break;
                    i = i+1;
                }
                while(A[j] >= p){    
                    if(j == (start+1)){
                        if(A[j] >= p)    //此时为分裂点右方全部是大于等于p的元素
                            return start;
                        break;
                    }
                    j = j-1;
                }
                swapArray(A,i,j);
            }
            swapArray(A,i,j);    //当i>=j撤换最后一次交换
            swapArray(A,j,start);
            return j;
        }
        
        /*
         * 交换数组中两个不同位置上的元素值
         */
        public static void swapArray(int[] A,int m,int n){
            int temp = A[m];
            A[m] = A[n];
            A[n] = temp;
        }
        
        //初始化一个随机数组
        public static int[] initArray(int n){
            int[] result = new int[n];
            for(int i = 0;i < n;i++)
                result[i] = (int)(Math.random()*100); //采用随机函数随机生成1~100之间的数
            return result;
                
        }
        
        public static void main(String[] args){
            int[] A = initArray(200);
            getQuicksort(A,0,(A.length-1));
            System.out.println();
            for(int i = 0;i < A.length;i++){
                if(i%10 == 0)
                    System.out.println();
                System.out.print(A[i]+"\t");
            }
        }
    }
    

    运行结果:

       0    0    0    1    1    1    2    2    2    
       2    3    3    4    4    4    7    7    7    
       8    8    8    9    9    11    12    12    12    
       13    14    14    15    15    16    16    17    17    
       18    19    19    19    20    20    21    23    24    
       24    24    25    25    25    25    25    26    26    
       27    27    28    28    28    29    29    29    30    
       31    31    34    34    34    35    36    37    37    
       40    40    41    42    42    43    44    44    44    
       45    45    45    47    48    48    48    50    50    
       50    50    51    51    52    53    55    55    56    
       56    57    57    58    58    58    59    60    60    
       62    63    63    63    64    65    65    65    65    
       66    67    68    69    69    69    70    70    72    
       72    74    75    75    76    76    76    76    77    
       77    78    79    79    80    81    81    81    81    
       82    82    83    83    84    84    86    86    86    
       87    87    87    87    87    87    87    87    88    
       89    89    89    90    92    93    93    93    95    
       96    96    96    97    98    98    99    99    99
    
    展开全文
  • 八大排序算法 一、直接插入 - 1.基本思路 - 2.代码实现 - 3....二、希尔排序 - 1....- 2....- 3....- 1....- 2....- 3....- 1....- 2....- 3....- 1....- 2....- 3....六、快速排序 - 1.基本思路 - 2.代码实现 - 3.时间复杂度和空间复杂度 七..
     
     
    

    八大排序算法

    一、直接插入

    1.基本思路

    在要排序的一组数中,假设前面(n-1) [n>=2] 个数已经是排好顺序的,现在要把第n个数插到前面的有序数中,使得这n个数也是排好顺序的。如此反复循环,直到全部排好顺序。

    2.代码实现

    • 1.遍历数组,每次循环从第二个数字往前插入
    • 2.设定插入数和得到已经排好序列的最后一个数的位数。temp和j=i-1。
    • 3.从最后一个数开始向前循环,如果插入数小于当前数,就将当前数向后移动一位。
    public static void insertSort(int[] data) {
        int temp;
        for(int i = 1;i < data.length; i++){// 取第i个数,插入前边的有序的序列
            temp = data[i];
            int j;
            for(j = i - 1; j>=0; j--) {// 从第i-1的位置上开始比较
                if(data[j] > temp) {// 若前面的数大,则往后挪一位
                    data[j+1] = data[j];
                } else {
                    break;// 否则,说明要插入的数比较大
                }
            }
            data[j+1] = temp;// 找到这个位置,插入数据
        }
    }
    

    3.时间复杂度和空间复杂度

    直接插入排序的平均复杂度为O(n²),最坏时间复杂度:O(n²),空间复杂度:O(1),没有分配内存。

    二、希尔排序

    针对直接插入排序下的效率问题,有人对此进行了改进与升级,这就是现在的希尔排序。希尔排序,也称递减增量排序算法,是插入排序的一种更高效的改进版本。希尔排序是非稳定排序算法。

    1.基本思路

    • 1.数的个数为length,i=length/2,将下标差值为i的数分为一组,构成有序序列。

    • 2.再取i=i/2 ,将下标差值为i的数分为一组,构成有序序列。

    • 3.重复第二步,直到k=1执行简单插入排序。

    思路:

    • 1.希尔排序(shell sort)这个排序方法又称为缩小增量排序,是1959年D·L·Shell提出来的。该方法的基本思想是:设待排序元素序列有n个元素,首先取一个整数increment(小于n)作为间隔将全部元素分为increment个子序列,所有距离为increment的元素放在同一个子序列中,在每一个子序列中分别实行直接插入排序。然后缩小间隔increment,重复上述子序列划分和排序工作。直到最后取increment=1,将所有元素放在同一个子序列中排序为止。
    • 2.由于开始时,increment的取值较大,每个子序列中的元素较少,排序速度较快,到排序后期increment取值逐渐变小,子序列中元素个数逐渐增多,但由于前面工作的基础,大多数元素已经基本有序,所以排序速度仍然很快。

    希尔排序举例:
    在这里插入图片描述

    2.代码实现

    • 1.遍历数组,每次循环从第二个数字往前插入
    • 2.设定插入数和得到已经排好序列的最后一个数的位数。temp和j=i-1。
    • 3.从最后一个数开始向前循环,如果插入数小于当前数,就将当前数向后移动一位。

    (1)首先确定每一组序列的下标的间隔,循环每次需要的间隔:int i = length/2; i >0 ; i /= 2

    (2)然后将每一组序列中元素进行插入排序,第二组第一个插入的数字是第一组第一个插入数字之后的那个数组,从i之后每个数字都要进行插入排序,就是插入的序列是各自不同的序列,不是一个一个子序列循环,而是在一个循环中for (int j=i;j<length;j++)完成所有子序列的插入排序。

    (3)直到i=0为止。

    public static void shellSort(int[] array) {
        int length = array.length;
        for (int i = length / 2; i > 0; i /= 2) {//序列的间隔,一直到间隔为一,这时候就只有一个子序列
            for (int j = i; j < length; j++) {//从i之后每个数字都要进行插入排序,就是插入的序列是各自不同的序列
                int temp = array[j];//里面就是直接插入算法
                int k;
                for (k = j - i; k >= 0; k -= i) {//实现各个数字插入排序到不同的序列中,直到间隔为1的时候,只有一个序列,就是完全的一个直接插入排序
                    if (temp < array[k]) {
                        array[k + i] = array[k];
                    } else {
                        break;
                    }
                }
                array[k + i] = temp;//把数字插入到位置上
            }
        }
        System.out.println(Arrays.toString(array));
    }
    

    3.时间复杂度和空间复杂度

    希尔排序的平均时间复杂度为O(n²),空间复杂度O(1) 。

    三、简单选择

    1.基本思路

    基本原理如下:对于给定的一组记录,经过第一轮比较后得到最小的记录,然后将该记录的位置与第一个记录的位置交换;接着对不包括第一个记录以外的其他记录进行第二次比较,得到最小记录并与第二个位置记录交换;重复该过程,直到进行比较的记录只剩下一个为止。

    2.代码实现

    • 1.确定要插入最小值的位置,从0开始到最后int i = 0; i <len ; i++
    • 2.将每次开始位置上的数字暂定为最小值min,从开始数字之后一个个和min比较,再把最小值存放到min
    • 3.将最小值所在位置上的数字和开始位置上的数字交换
    public static void selectSort(int[] array) {
        int len = array.length;
        for (int i = 0; i < len; i++) {//确定每次开始的位置
            int min = array[i];//设定开始数字为最小的值最小值
            int flag = i;
            for (int j = i + 1; j < len; j++) {//把最小值存放到min,从开始数字向后一个个和min比较,再把最小值存放到min
                if (min > array[j]) {
                    min = array[j];
                    flag = j;
                }
            }
            if (flag != i) {
                array[flag] = array[i];
                array[i] = min;
            }
        }
        System.out.println(Arrays.toString(array));
    }
    

    3.时间复杂度和空间复杂度

    简单选择排序的时间复杂度为O(n²)

    四、堆排序

    1.基本思路

    • 1.若array[0,…,n-1]表示一颗完全二叉树的顺序存储模式,则双亲节点指针和孩子结点指针之间的内在关系如下:
    任意一节点指针 i:
    父节点:i==0 ? null : (i-1)/2
    左孩子:2*i + 1
    右孩子:2*i + 2
    
    • 2.堆得定义
    n个关键字序列array[0,...,n-1],当且仅当满足下列要求:(0 <= i <= (n-1)/2)
    ① array[i] <= array[2*i + 1] 且 array[i] <= array[2*i + 2]; 称为小根堆;
    ② array[i] >= array[2*i + 1] 且 array[i] >= array[2*i + 2]; 称为大根堆;
    
    • 3.建立大顶堆

    n个节点的完全二叉树array[0,…,n-1],最后一个节点n-1是第(n-1-1)/2个节点的孩子。对第(n-1-1)/2个节点为根的子树调整,使该子树称为堆。

    对于大根堆,调整方法为:若【根节点的关键字】小于【左右子女中关键字较大者】,则交换。

    之后向前依次对各节点((n-2)/2 - 1)~ 0为根的子树进行调整,看该节点值是否大于其左右子节点的值,若不是,将左右子节点中较大值与之交换,交换后可能会破坏下一级堆,于是继续采用上述方法构建下一级的堆,直到以该节点为根的子树构成堆为止。

    反复利用上述调整堆的方法建堆,直到根节点。

    • 4.堆排序(大顶堆)
    ①将存放在array[0,...,n-1]中的n个元素建成初始堆;
    ②将堆顶元素与堆底元素进行交换,则序列的最大值即已放到正确的位置;
    ③将数组中array[0,...,n-1]前n-1个元素再次形成大根堆,再重复第②③步,直到堆中仅剩下一个元素为止。
    

    2.代码实现

    
    /**
        *  大顶堆排序
        * @param array
        */
    public static void maxHeapSort(int[] array) {
        int i;
        int len = array.length;
        // 构建大顶堆
        for (i = len / 2 - 1; i >= 0; i--) {
            adjustMaxHeap(array, i, len);
        }
        // 堆顶是最大值,交换堆顶和最后一个数,再重新调整最大堆,下一次循环   i--
        for (i = len - 1; i >= 0; i--) {
            int temp = array[0];
            array[0] = array[i];
            array[i] = temp;
            adjustMaxHeap(array, 0, i);
        }
        System.out.println(Arrays.toString(array));
    }
    
    private static void adjustMaxHeap(int[] a, int pos, int len) {
        int temp;
        int child;
        for (temp = a[pos]; 2 * pos + 1 < len; pos = child) {
            // 数组从0开始,r(i)>=r(2i) r(i)>=r(2i+1)  对应 pos => 2 * pos + 1 和 2 * pos +2
            child = 2 * pos + 1;
            // 有右孩子,且右孩子数值更大
            if (child + 1 < len && a[child] < a[child + 1]) {
                child++;
            }
            // 最大的孩子大于根节点
            if (a[child] > temp) {
                a[pos] = a[child];
            } else {
                break;
            }
        }
        a[pos] = temp;
    }
    

    3.时间复杂度和空间复杂度

    时间复杂度:建堆:o(n),每次调整o(log n),故最好、最坏、平均情况下:o(n*logn);

    五、冒泡排序

    1.基本思路

    一次冒泡将序列中从头到尾所有元素两两比较,将最大的放在最后面。

    将剩余序列中所有元素再次两两比较,将最大的放在最后面。

    重复第二步,直到只剩下一个数。

    2.代码实现

    /**
     * @author fupeng
     * 冒泡排序优化第二版
     * 第一版优化增加flag标记,没有数字交换直接return,最优时间复杂度O(n)
     * 第二版优化,增加tempPosition记录内循环最后一次交换的位置,来缩减内循环的次数
     */
    public static void bubbleSort(int[] array) {
        int len = array.length - 1;
        // 开辟一个临时空间, 存放交换的中间值
        int temp;
        // 记录最后一次交换的位置
        int tempPosition = 0;
        // 要遍历的次数
        for (int i = 0; i < array.length - 1; i++) {
            int flag = 1; // 设置一个标志位
            // 依次比较相邻两个数的大小,遍历一次后,会将前面没有排好序的最大值放到后面位置
            for (int j = 0; j < len; j++) {
                // 比较相邻的元素,如果前面的数大于后面的数,交换
                if (array[j] > array[j + 1]) {
                    temp = array[j + 1];
                    array[j + 1] = array[j];
                    array[j] = temp;
                    // 发生交换,标志位置0
                    flag = 0;
                    // 记录交换的位置
                    tempPosition = j;
                }
            }
            // 把最后一次交换的位置给len,来缩减内循环的次数
            len = tempPosition;
            // 如果没有交换过元素,则已经有序
            if (flag == 1) {
                System.out.println(Arrays.toString(array));
                return;
            }
        }
        System.out.println(Arrays.toString(array));
    }
    

    3.时间复杂度和空间复杂度

    冒泡排序的最好时间复杂度为O(n),最坏时间复杂度为O(n²),平均时间复杂度为O(n²),空间复杂度为O(1),它是一种稳定的排序算法。

    六、快速排序

    1.基本思路

    快速排序使用分治策略来把一个序列(list)分为两个子序列(sub-lists)。步骤为:

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

    递归到最底部时,数列的大小是零或一,也就是已经排序好了。这个算法一定会结束,因为在每次的迭代(iteration)中,它至少会把一个元素摆到它最后的位置去。

    2.代码实现

    public static void quickSort(int[] array) {
        sort(array, 0, array.length - 1);
        System.out.println(Arrays.toString(array));
    }
    
    private static void sort(int[] a, int low, int high) {
        int i = low;
        int j = high;
        if (a.length <= 1) {
            return;
        }
        if (i >= j) {
            return;
        }
        int index = a[i];
        while (i < j) {
            while (i < j && a[j] >= index)
                j--;
            if (a[j] < index)
                a[i++] = a[j];
            while (i < j && a[i] <= index)
                i++;
            if (a[i] > index)
                a[j--] = a[i];
        }
        a[i] = index;
        sort(a, low, i - 1);
        sort(a, i + 1, high);
    }
    

    3.时间复杂度和空间复杂度

    虽然 快排的时间复杂度达到了 O(n²),但是在大多数情况下都比平均时间复杂度为 O(n logn) 的排序算法表现要更好。

    七、归并排序

    1.基本思路

    归并排序(MERGE-SORT)是利用归并的思想实现的排序方法,该算法采用经典的分治(divide-and-conquer)策略(分治法将问题分(divide)成一些小的问题然后递归求解,而治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起,即分而治之)。

    • 1.分而治之
      在这里插入图片描述

    可以看到这种结构很像一棵完全二叉树,本文的归并排序我们采用递归去实现(也可采用迭代的方式去实现)。分阶段可以理解为就是递归拆分子序列的过程,递归深度为log2n。

    • 2.合并相邻有序子序列
      再来看看治阶段,我们需要将两个已经有序的子序列合并成一个有序序列,比如上图中的最后一次合并,要将[4,5,7,8]和[1,2,3,6]两个已经有序的子序列,合并为最终序列[1,2,3,4,5,6,7,8],来看下实现步骤。

    在这里插入图片描述
    在这里插入图片描述

    2.代码实现

    public static void mergeSort(int[] array) {
        int[] temp = new int[array.length];// 在排序前,先建好一个长度等于原数组长度的临时数组,避免递归中频繁开辟空间
        mergeSort(array, 0, array.length-1, temp);
        System.out.println(Arrays.toString(array));
    }
    
    private static void mergeSort(int[] arr, int left, int right, int []temp) {
        if(left < right) {
            int mid = (left+right) / 2;
            mergeSort(arr, left, mid, temp);// 左边归并排序,使得左子序列有序
            mergeSort(arr, mid+1, right, temp);// 右边归并排序,使得右子序列有序
            merge(arr, left, mid, right, temp);// 将两个有序子数组合并操作
        }
    }
    
    private static void merge(int[] arr, int left, int mid, int right, int[] temp) {
        int i = left;// 左序列指针
        int j = mid+1;// 右序列指针
        int t = 0;// 临时数组指针
        while (i <= mid && j <= right) {
            if(arr[i] <= arr[j]) {
                temp[t++] = arr[i++];
            } else {
                temp[t++] = arr[j++];
            }
        }
        while(i <= mid) {// 将左边剩余元素填充进temp中
            temp[t++] = arr[i++];
        }
        while(j <= right) {// 将右序列剩余元素填充进temp中
            temp[t++] = arr[j++];
        }
        t = 0;
        // 将temp中的元素全部拷贝到原数组中
        while(left <= right) {
            arr[left++] = temp[t++];
        }
    }
    

    3.时间复杂度和空间复杂度

    归并排序是稳定排序,它也是一种十分高效的排序,能利用完全二叉树特性的排序一般性能都不会太差。java中Arrays.sort()采用了一种名为TimSort的排序算法,就是归并排序的优化版本。从上文的图中可看出,每次合并操作的平均时间复杂度为O(n),而完全二叉树的深度为|log2n|。总的平均时间复杂度为O(nlogn)。而且,归并排序的最好,最坏,平均时间复杂度均为O(nlogn)。

    八、基数排序

    1.基本思路

    • 1.基数排序的思想就是先排好各位,然后排好各位的基础上排十位,以此类推,直到遍历最高位 次,排序结束(仔细理解最后一句话)
    • 2.基数排序不是比较排序,而是通过分配和收集的过程来实现排序
    • 3.初始化10个桶(固定的),桶下标为0-9
    • 4.通过得到待排序数字的个十百等位的数字,把这个数字对应的item放到对应的桶中
    • 5.基数排序有两种排序方式:LSD和MSD,最小位优先(从右边开始)和最大位优先(从左边开始)

    在这里插入图片描述

    2.代码实现

    public static void radixSort(int[] array) {
        ArrayList<ArrayList<Integer>> queue = new ArrayList<>();
        for (int i = 0; i <10 ; i++) {
            queue.add(new ArrayList<>());// 创建一个基数从0---9 每个数字上都是一个list
        }
        // 找到最大值,并判断最大值是几位数
        int max = array[0];
        for (int i = 1; i < array.length; i++) {
            if (max < array[i]) {
                max = array[i];
            }
        }
        int time = 0;
        while (max > 0) {
            max /= 10;
            time++;
        }
        for (int i = 0; i < time; i++) {// 循环每一个位数(个位、十位、百位)
            for (int j = 0; j < array.length; j++) {// 循环数组,取每一个值
                int x = array[j] % (int) Math.pow(10, i + 1) / (int) Math.pow(10, i);
                ArrayList<Integer> queue3 = queue.get(x);
    
                queue3.add(array[j]);
                queue.set(x, queue3);
            }
            int count = 0;
            for (int k = 0; k < 10; k++) {
                while (queue.get(k).size() > 0) {
                    ArrayList<Integer> queue4 = queue.get(k);
                    array[count] = queue4.get(0);
                    queue4.remove(0);
                    count++;
                }
            }
        }
    }
    

    3.时间复杂度和空间复杂度

    归并排序是稳定排序,它也是一种十分高效的排序,能利用完全二叉树特性的排序一般性能都不会太差。java中Arrays.sort()采用了一种名为TimSort的排序算法,就是归并排序的优化版本。从上文的图中可看出,每次合并操作的平均时间复杂度为O(n),而完全二叉树的深度为|log2n|。总的平均时间复杂度为O(nlogn)。而且,归并排序的最好,最坏,平均时间复杂度均为O(nlogn)。

    总结

    在这里插入图片描述

    引用:

    https://www.cnblogs.com/mensan/p/10570050.html

    https://www.cnblogs.com/jyroy/p/11248691.html

    https://www.cnblogs.com/chengxiao/p/6194356.html

    https://www.jianshu.com/p/8340dfaea3af

    展开全文
  • java快速排序,优化

    2016-03-04 17:02:09
    快速排序优化,尽可能少的循环、交换。

    java快速排序优化

    研究java快速排序ing,目前希望做到,尽可能少的循环、交换。(求指点)

    (话说回来是判断连个值大小快,还是交换两个值快。我是凭感觉,认为判断连个大小快,所以当前版本判断比较多。)

    快速排序原理:从数据序列中选一个元素,并将序列中所有比该元素小的元素都放到它的右边或左边,再对左右两边分别用同样的方法处之直到每一个待处理的序列的长度为1, 处理结束。

    话不多说,先上我的源码:

    public static void quickSort(int[] data,int left,int right){
    		int split=data[right];//分割值,以这个值作为分割data的的标准。
    		int pointerIndex=left;//相当于指针,记录下标,指针左端的都是小于split值的,指针右端的都是大于split值的
    		for(int i=left;i<right;i++){
    			if(data[i]<split){
    				if(i!=pointerIndex){
    					data[i]=data[i]^data[pointerIndex];
    					data[pointerIndex]=data[i]^data[pointerIndex];
    					data[i]=data[i]^data[pointerIndex];
    				}
    				pointerIndex++;
    			}
    		}
    		//如果pointerIndex不是最右端,那么交换这两个下表对应的值。
    		//ps:其实,如果这两个值是相等的话可以不交换,个人感觉最好在加上一个判断data[pointerIndex]!=data[right]
    		//if(pointerIndex!=right){
    		if(pointerIndex!=right&&data[pointerIndex]!=data[right]){
    			data[right] = data[pointerIndex]^data[right];
    			data[pointerIndex]=data[right]^data[pointerIndex];
    			data[right]=data[right]^data[pointerIndex];
    		}
    		if(pointerIndex-1>left){//如果pointerIndex-1==left,说明左端只有一个数,那么左端就无需排序。
    			quickSort(data,left,pointerIndex-1);
    		}
    		if(pointerIndex+1<right){//如果pointerIndex+1==right,说明右端只有一个数,那么右端无需排序。
    			quickSort(data,pointerIndex+1,right);
    		}
    	}

    测试代码:

    public class QuickTest {
    
    	private static int iterationNumber;
    	private static int swapNumber;
    	
    	public static void main(String[]args){
    //		int[] a={0,3,10,13,5,6,7,1,7,22,2,4,8,12,9};
    //		int[] a={0,3,10,13,5,6,7,1,7,22,2,4,8,12,29};
    //		int[] a={17,4,2,3,7,9,5,1,15,4,3,6,11,8,0,10,19,14,16,12,18,13};
    		int[] a={17,18,4,2,3,7,9,5,1,15,4,8,0,10,19,13,14,16,12,3,6,11,13};
    		quickSort(a,0,a.length-1);
    
    		System.out.println("iterationNumber:"+iterationNumber+"   swapNumber:"+swapNumber);
    		System.out.println(Arrays.toString(a));
    	}
    	
    	public static void quickSort(int[] data,int left,int right){
    		int split=data[right];//分割值,以这个值作为分割data的的标准。
    		int pointerIndex=left;//相当于指针,记录下标,指针左端的都是小于split值的,指针右端的都是大于split值的
    		for(int i=left;i<right;i++){
    			if(data[i]<split){
    				if(i!=pointerIndex){
    					data[i]=data[i]^data[pointerIndex];
    					data[pointerIndex]=data[i]^data[pointerIndex];
    					data[i]=data[i]^data[pointerIndex];
    					swapNumber++;
    					System.out.println("i="+i+" - "+data[i]+"与"+data[pointerIndex]+"交换: "+Arrays.toString(data));
    				}
    				pointerIndex++;
    			}
    		}
    		//如果pointerIndex不是最右端,那么交换这两个下表对应的值。
    		//ps:其实,如果这两个值是相等的话可以不交换,个人感觉最好在加上一个判断data[pointerIndex]!=data[right]
    		//if(pointerIndex!=right){
    		if(pointerIndex!=right&&data[pointerIndex]!=data[right]){
    			data[right] = data[pointerIndex]^data[right];
    			data[pointerIndex]=data[right]^data[pointerIndex];
    			data[right]=data[right]^data[pointerIndex];
    			swapNumber++;
    			System.out.println(data[right]+"与"+data[pointerIndex]+"交换: "+Arrays.toString(data));
    		}
    		if(pointerIndex-1>left){//如果pointerIndex-1==left,说明左端只有一个数,那么左端就无需排序。
    			iterationNumber++;
    			quickSort(data,left,pointerIndex-1);
    		}
    		if(pointerIndex+1<right){//如果pointerIndex+1==right,说明右端只有一个数,那么右端无需排序。
    			iterationNumber++;
    			quickSort(data,pointerIndex+1,right);
    		}
    	}
    }


    展开全文
  • 快速排序

    万次阅读 多人点赞 2017-03-18 18:11:48
    快速排序
  • Java知识体系最强总结(2021版)

    万次阅读 多人点赞 2019-12-18 10:09:56
    本人从事Java开发已多年,平时有记录问题解决方案和总结知识点的习惯,整理了一些有关Java的知识体系,这不是最终版,会不定期的更新。也算是记录自己在从事编程工作的成长足迹,通过博客可以促进博主与阅读者的共同...
  • Java实现快速排序(快排)

    万次阅读 多人点赞 2018-09-07 02:12:49
    快速排序是冒泡排序的改进版,也是最好的一种内排序,在很多面试题中都会出现,也是作为程序员必须掌握的一种排序方法。 快速排序由C. A. R. Hoare在1962年提出。它的基本思想是:通过一趟排序将要排序的数据分割成...
  • 图解java实现快速排序算法

    千次阅读 2018-02-07 16:53:39
    ...假如我们的计算机每秒钟可以运行10亿次,那么对1亿个数进行排序,桶排序则只需要0.1秒,而冒泡排序则需要1千万秒,达到115天之久,是不是很吓人。那有没有既不浪费空间又可以快一点的排序
  • 快速排序(QuickSort)算法Java实现

    千次阅读 2020-06-24 20:38:31
    百度了一下“java快速排序”,出来的一堆博客,和《啊哈算法》的同出一路,我的疑惑没有得到解答,不免有点失望。 自古评论区出人才,有意思的来了,我一看这几篇博客的评论区,果然是一片哀嚎,看来困惑的不只是我...
  • 首先我们了解下什么是冒泡排序: 介绍 冒泡排序属于一种简单的排序,也是经典的一种排序思想。 原理:比较两个相邻的元素,将值大或小的元素交换至右端(相邻位置作交换)。 思路:依次比较相邻的两个数,将...
  • Java数组:快速排序

    2019-11-04 12:42:47
    Java 数组的快速排序 快速排序思想 快速排序的思想通过先选择一个基准点,然后通过左右两个指针先后遍历,并且依次比较数值与基准点的大小,比基准点大的数据放到右边,比基本点小的数据放到左右。在循环遍历左右...
  • public class Java_SortMethod { static int temp; public static void main(String[]args) { int [] arr1 = new int[] {4,8,7,-6,5,0,2,3,9,1,-8,-9}; int [] arr2 = new int[] {4,8,7,-6...
  • java实现快速排序和随机快速排序

    千次阅读 2016-05-12 16:31:56
    快速排序快速排序的随机化版本性能分析 随机序列10w100w1000w有序序列10w1w1000w 排序算法是算法学习的第一步,想当初我学的第一个算法就是选择排序,不过当时很长一段时间我都不清楚我到底用的是...
  • Java快速排序总结

    千次阅读 2015-10-12 17:24:45
    在自己做过的java项目中呢,确实没有自己写过排序到项目中去,而自己掌握的只是一个简单的冒泡排序,随着时间的积累,对于程序的性能也越来越关注,因此也更加关注于自己的技能细节方面的改进,因此今天来写一下快速...
  • 快速排序——JAVA实现(图文并茂)

    万次阅读 多人点赞 2018-08-10 16:07:23
    那就是“快速排序”啦!光听这个名字是不是就觉得很高端呢。 假设我们现在对“6 1 2 7 9 3 4 5 10 8”这个10个数进行排序。首先在这个序列中随便找一个数作为基准数(不要被这个名词吓到了,就是一个用来参照的数,...
  • java实现快速排序算法

    万次阅读 2019-01-20 10:26:30
    3.当左边和右边同时指向一个值v(比c小,因为是从右边开始递减的),会退出当前循环。 4.交换c和v的值,返回v所在的地址。 5.递归,以此类推 public class QuickSort { public static int[] quickSort(int[] a,in....
  • Java实现快速排序算法

    千次阅读 2019-09-22 12:45:03
    快速排序 快速排序使用分治法(Divide and conquer)策略来把一个序列(list)分为两个子序列(sub-lists)。 步骤为: 从数列中挑出一个元素,称为"基准"(pivot), 重新排序数列,所有比基准值小的元素摆放在...
  • 6、快速排序(Quick Sort) 快速排序的基本思想:通过一趟排序将待排记录分隔成独立的两部分,其中一部分记录的关键字均比另一部分的关键字小,则可分别对这两部分记录继续进行排序,以达到整个序列有序。 6.1 ...
  • 快速排序 --Java版本

    千次阅读 2017-08-15 14:22:06
    目录1、快速排序解释2、快速排序大白话(认真看)3、代码展示4、结果展示——————————————————————————————-1、快速排序解释 快速排序(Quicksort)是对冒泡排序的一种改进。...
  • //循环实现public class QuickStack { public static void print(int[] arr){ for(int n=0;n&lt;arr.length;n++){ System.out.print(arr[n]+" "); } System.out.println(); }...
  • Java-list,快速排序

    千次阅读 2018-09-13 16:38:51
    Java-list,快速排序 学海无涯,回头就忘! 而立之年开始学习java,各位加油! 场景描述 对一个list的内容,按照字母(或者数字)进行排序(一,如果是数字,用int大小对比;二,如果是字母String,可以取第一...
  • Java排序(冒泡排序、快速排序

    千次阅读 2019-01-22 15:09:36
    一、冒泡排序:  冒泡算法原理:冒泡算法就是依次比较数组中相邻的两个元素,如果左边比右边大则进行调换,以此类推,这样第一次排序就把最大的元素放在最底下。 举例说明:要排序数组:int[] arr = {7, 2, 6, 5,...
  • Java实现数组的快速排序快速排序算法) &lt;a class="follow-nickName" href="https://me.csdn.net/gg543012991" target="_blank"&gt;安...
  • 实现快速排序算法的关键在于先在数组中选择一个数字,接下来把数组中的数字分为两部分,比选择数字小的数字移动到数组的左边,比选择数字大的数字移动到数组的右边。 具体的实现算法为: 设要排序的数组是A[0]……...
  • 快速排序Java版(递归与非递归)

    千次阅读 2019-07-03 19:36:29
    快速排序Java版) 听名字就很diao,直接上干货。(杠精别打我,支点的英文是pivot,我全拼错了) 快排一定要思路清晰,没事多写几遍,要不容易忘。 对于一个数组对它进行排序,快排的思想就是交换交换再交换,我们...
  • 递归实现快速排序

    2020-12-21 20:49:47
    以前学习数据结构的时候写快排用的循环都是双重for循环,今天偶尔看到了运用递归来实现快速排序,所以突发想记录一下。由于我以前学过c和java,现在在自学python,所以一下代码均为python。但基本思想是一样的。 1....
  • 快速排序java代码实现

    千次阅读 2018-03-01 14:57:22
    说明: 快速排序是一个速度非常快的交换排序算法,它的基本思路很简单,从待排的数据序列中任取一个数据(如第一个数据)作为基准值,所有比它小的元素放到左边,所有比它大的元素放到右边。经过这样一趟下来,该...
  • 给定值的快速排序` import java.util.*; public class Program_kuaipai { public static void main(String[] args) { String str = "12 34 1 -5 9 100 55 0"; String[] numStrs = str.split(&...
  • JAVA快速排序——亿级体量数据

    千次阅读 2016-08-26 19:05:17
    算法真的是太强大了,今天测试了给一亿个随机数据进行排序,花了67秒不到!不多说,直接见代码:  import java.util.Random; public class sort {    public static void main(String[] args...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 52,255
精华内容 20,902
关键字:

java快速排序for循环

java 订阅