精华内容
下载资源
问答
  • 舞动的排序算法 快速排序 通过动画演示快速排序,很好的学习,课程资源。
  • 十大排序算法快速排序之Java实现

    万次阅读 2020-07-19 14:10:11
    快速排序 快速排序(Quick Sort)是对冒泡排序的一种改进,采用的是分治策略(一般与递归结合使用),以减少排序过程中的比较次数。 快速排序在1960年由查尔斯·安东尼·理查德·霍尔(Charles Antony Richard Hoare...

    快速排序

    快速排序(Quick Sort)是对冒泡排序的一种改进,采用的是分治策略(一般与递归结合使用),以减少排序过程中的比较次数。

    快速排序在1960年由查尔斯·安东尼·理查德·霍尔(Charles Antony Richard Hoare,缩写为C. A. R. Hoare)提出,昵称为东尼·霍尔(Tony Hoare)。

    算法步骤

    1. 从数组中选择一个轴点元素(pivot),假设每次都选择索引为0的元素为轴点元素。
    2. 利用pivot将数组分割成2个子数组,将小于pivot的元素放在pivot前面(左侧),将大于pivot的元素放在pivot后面(右侧),等于pivot的元素放哪边都可以。
    3. 递归对子序列进行前面两步操作,直到不能再分割(子序列中只剩下1个元素)。

    快速排序的本质:逐渐将每一个元素都转换成轴点元素。

    在这里插入图片描述

    动图演示

    在这里插入图片描述

    代码实现

    package com.morris.data.struct.sort.cmp;
    
    import com.morris.data.struct.sort.AbstractSort;
    
    /**
     * 快速排序
     */
    public class QuickSort<E extends Comparable> extends AbstractSort<E> {
    
        @Override
        protected void sort() {
            sort(0, array.length);
        }
    
        private void sort(int begin, int end) {
    
            if(end - begin < 2) {
                return;
            }
    
            int pivotIndex = pivotIndex(begin, end);
    
            sort(begin, pivotIndex);
            sort(pivotIndex + 1, end);
    
        }
    
        /**
         * 返回轴点元素的真正索引
         * @param begin
         * @param end
         * @return
         */
        private int pivotIndex(int begin, int end) {
    
            // 随机选择一个元素跟begin位置进行交换,为了降低最好时间复杂度
            swap(begin, begin + (int)(Math.random() * (end - begin)));
    
            E pivot = array[begin];
            end--;
    
            while (begin < end) {
    
                while (begin < end) {
                    // 从右向左扫描
                    if(cmp(array[end], pivot) < 0) {
                        array[begin++] = array[end];
                        break;
                    } else {
                        end--;
                    }
                }
    
                while (begin < end) {
                    // 从左向右扫描
                    if(cmp(array[begin], pivot) > 0) {
                        array[end--] = array[begin];
                        break;
                    } else {
                        begin++;
                    }
                }
            }
    
            array[begin] = pivot; // begin==end
    
            return begin;
        }
    }
    

    在轴点左右元素数量比较均匀的情况下,同时也是最好的情况,所以最好时间复杂度和平均时间复杂度均为O(nlogn)。

    如果轴点左右元素数量极度不均匀就会出现最坏情况,所以最坏时间复杂度为O(n^2)。

    为了降低最坏情况的出现概率,一般采取的做法是:随机选择轴点元素。

    由于递归调用的缘故,所以空间复杂度为O(logn)。

    对相等元素的处理

    当代码中下面两处的比较为<或>时,快速排序对相等元素的处理过程如下:

    ...
    // 从右向左扫描
    if(cmp(array[end], pivot) < 0) {
    ...
    ...
    // 从左向右扫描
    if(cmp(array[begin], pivot) > 0) {
    ...
    

    在这里插入图片描述

    如果数组中的所有元素都与轴点元素相等,利用目前的算法实现,轴点元素可以将数组分割成2个均匀的子序列。

    当代码中下面两处的比较为<=或>=时,快速排序对相等元素的处理过程如下:

    ...
    // 从右向左扫描
    if(cmp(array[end], pivot) <= 0) {
    ...
    ...
    // 从左向右扫描
    if(cmp(array[begin], pivot) >= 0) {
    ...
    

    在这里插入图片描述
    根据轴点元素分割出来的子数组极度不均匀,会导致出现最坏时间复杂度O(n^2)。

    更多精彩内容关注本人公众号:架构师升级之路
    在这里插入图片描述

    展开全文
  • 算法基础 参加ACM掌握算法 经典排序和查找算法
  • 算法 - 快速排序(C#)

    万次阅读 多人点赞 2019-01-29 20:29:11
    分享一个大牛的人工智能教程。零基础!通俗易懂!风趣幽默!希望你也加入到人工智能的队伍中来!... /* * 快速排序(QuickSort)是对冒泡排序的一种... * 然后再按此方法对这两部分数据分别进行快速排序,整个排序...

    分享一个大牛的人工智能教程。零基础!通俗易懂!风趣幽默!希望你也加入到人工智能的队伍中来!请点击http://www.captainbed.net

    /*
     * 快速排序(QuickSort)是对冒泡排序的一种改进。它的基本思想是:
     * 通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据要小,
     * 然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。
     *
     * 设要排序的数组是a[0]...a[N-1],首先任意选取一个数据(通常选用数组的首元素)作为关键数据,
     * 然后将所有比它小的数都放到它的前面,所有比它大的数都放到它的后面,这个过程称为一趟快速排序。
     * 值得注意的是,快速排序不是一种稳定的排序算法,也就是说,多个相同值数据的相对位置也许会在算法结束时产生变动。
     * 
     * 一趟快速排序的算法是:
     * 1)设置两个变量i、j,排序开始的时候:i=0,j=N-1;
     * 2)以数组首元素作为关键数据,赋值给pivot,即pivot=a[0];
     * 3)从j开始向前搜索,即由后开始向前搜索(j--),找到第一个小于pivot的值a[j],将a[j]赋值给a[i];
     * 4)从i开始向后搜索,即由前开始向后搜索(i++),找到第一个大于pivot的值a[i],将a[i]赋值给a[j];
     * 5)重复第3、4步,直到i==j;(在3、4步中,若没找到符合条件的值,即第3步中a[j]不小于pivot,
     * 第4步中a[i]不大于pivot的时候改变j、i的值,使得j=j-1,i=i+1,直至找到为止。
     * 若找到符合条件的值,进行替换的时候i、j指针位置不变。)
     *
     * 快速排序的平均时间复杂度是:O(nlog<sub>2</sub>n)。
     */
    
    namespace QuickSort
    {
        using System;
    
        public static class Program
        {
            /// <summary>
            /// The main.
            /// </summary>
            public static void Main()
            {
                int[] a = {101, 93, 856, 7, 62, 15, 84, 3, 298, 1256};
    
                Console.WriteLine("Before Quick Sort:");
                foreach (int i in a)
                {
                    Console.Write(i + " ");
                }
    
                Console.WriteLine("\r\n");
    
                Console.WriteLine("In Quick Sort:");
                QuickSort(a, 0, 9);
    
                Console.WriteLine("\r\nAfter Quick Sort:");
                foreach (int i in a)
                {
                    Console.Write(i + " ");
                }
            }
    
            /// <summary>
            /// 快速排序。
            /// </summary>
            /// <param name="a">
            /// 待排序数组。
            /// </param>
            /// <param name="low">
            /// 待排序数组的排序起始位置。
            /// </param>
            /// <param name="high">
            /// 待排序数组的排序终止位置。
            /// </param>
            private static void QuickSort(int[] a, int low, int high)
            {
                if (low >= high)
                {
                    return;
                }
    
                int pivot = QuickSortOnce(a, low, high);
    
                // 输出每一次排序。
                foreach (int i in a)
                {
                    Console.Write(i + " ");
                }
    
                Console.WriteLine(string.Empty);
    
                // 对枢轴的左端进行排序。
                QuickSort(a, low, pivot - 1);
    
                // 对枢轴的右端进行排序。
                QuickSort(a, pivot + 1, high);
            }
    
            /// <summary>
            /// 一趟快速排序。
            /// </summary>
            /// <param name="a">
            /// 待排序数组。
            /// </param>
            /// <param name="low">
            /// 待排序数组的排序起始位置。
            /// </param>
            /// <param name="high">
            /// 待排序数组的排序终止位置。
            /// </param>
            /// <returns>
            /// 返回枢轴的位置。
            /// </returns>
            private static int QuickSortOnce(int[] a, int low, int high)
            {
                // 将首元素作为枢轴。
                int pivot = a[low];
                int i = low, j = high;
    
                while (i < j)
                {
                    // 从右到左,寻找首个小于pivot的元素。
                    while (a[j] >= pivot && i < j)
                    {
                        j--;
                    }
    
                    // 执行到此,j一定指向从右端起首个小于或等于pivot的元素。执行替换。
                    a[i] = a[j];
    
                    // 从左到右,寻找首个大于pivot的元素。
                    while (a[i] <= pivot && i < j)
                    {
                        i++;
                    }
    
                    // 执行到此,i一定指向从左端起首个大于或等于pivot的元素。执行替换。
                    a[j] = a[i];
                }
    
                // 退出while循环,执行至此,必定是i==j的情况。i(或j)指向的即是枢轴的位置,定位该趟排序的枢轴并将该位置返回。
                a[i] = pivot;
                return i;
            }
        }
    }
    
    // Output:
    /*
    Before Quick Sort:
    101 93 856 7 62 15 84 3 298 1256
    
    In Quick Sort:
    3 93 84 7 62 15 101 856 298 1256
    3 93 84 7 62 15 101 856 298 1256
    3 15 84 7 62 93 101 856 298 1256
    3 7 15 84 62 93 101 856 298 1256
    3 7 15 62 84 93 101 856 298 1256
    3 7 15 62 84 93 101 298 856 1256
    
    After Quick Sort:
    3 7 15 62 84 93 101 298 856 1256
    */

     

    展开全文
  • 白话经典算法系列之六 快速排序 快速搞定

    万次阅读 多人点赞 2011-08-13 17:19:58
    快速排序由于排序效率在同为O(N*logN)的几种排序方法中效率较高,因此经常被采用,再加上快速排序思想----分治法也确实实用,因此很多软件公司的笔试面试,包括像腾讯,微软等知名IT公司都喜欢考这个,还有大大小的...
     
    快速排序由于排序效率在同为O(N*logN)的几种排序方法中效率较高,因此经常被采用,再加上快速排序思想----分治法也确实实用,因此很多软件公司的笔试面试,包括像腾讯,微软等知名IT公司都喜欢考这个,还有大大小的程序方面的考试如软考,考研中也常常出现快速排序的身影。
    

    总的说来,要直接默写出快速排序还是有一定难度的,因为本人就自己的理解对快速排序作了下白话解释,希望对大家理解有帮助,达到快速排序,快速搞定

     

    快速排序是C.R.A.Hoare于1962年提出的一种划分交换排序。它采用了一种分治的策略,通常称其为分治法(Divide-and-ConquerMethod)。

    该方法的基本思想是:

    1.先从数列中取出一个数作为基准数。

    2.分区过程,将比这个数大的数全放到它的右边,小于或等于它的数全放到它的左边。

    3.再对左右区间重复第二步,直到各区间只有一个数。

     

    虽然快速排序称为分治法,但分治法这三个字显然无法很好的概括快速排序的全部步骤。因此我的对快速排序作了进一步的说明:挖坑填数+分治法

    先来看实例吧,定义下面再给出(最好能用自己的话来总结定义,这样对实现代码会有帮助)。

     

    以一个数组作为示例,取区间第一个数为基准数。

    0

    1

    2

    3

    4

    5

    6

    7

    8

    9

    72

    6

    57

    88

    60

    42

    83

    73

    48

    85

    初始时,i = 0;  j = 9;   X = a[i] = 72

    由于已经将a[0]中的数保存到X中,可以理解成在数组a[0]上挖了个坑,可以将其它数据填充到这来。

    从j开始向前找一个比X小或等于X的数。当j=8,符合条件,将a[8]挖出再填到上一个坑a[0]中。a[0]=a[8]; i++;  这样一个坑a[0]就被搞定了,但又形成了一个新坑a[8],这怎么办了?简单,再找数字来填a[8]这个坑。这次从i开始向后找一个大于X的数,当i=3,符合条件,将a[3]挖出再填到上一个坑中a[8]=a[3]; j--;

     

    数组变为:

    0

    1

    2

    3

    4

    5

    6

    7

    8

    9

    48

    6

    57

    88

    60

    42

    83

    73

    88

    85

     i = 3;   j = 7;   X=72

    再重复上面的步骤,先从后向前找,再从前向后找

    从j开始向前找,当j=5,符合条件,将a[5]挖出填到上一个坑中,a[3] = a[5]; i++;

    从i开始向后找,当i=5时,由于i==j退出。

    此时,i = j = 5,而a[5]刚好又是上次挖的坑,因此将X填入a[5]。

     

    数组变为:

    0

    1

    2

    3

    4

    5

    6

    7

    8

    9

    48

    6

    57

    42

    60

    72

    83

    73

    88

    85

    可以看出a[5]前面的数字都小于它,a[5]后面的数字都大于它。因此再对a[0…4]和a[6…9]这二个子区间重复上述步骤就可以了。

     

     

    对挖坑填数进行总结

    1.i =L; j = R; 将基准数挖出形成第一个坑a[i]。

    2.j--由后向前找比它小的数,找到后挖出此数填前一个坑a[i]中。

    3.i++由前向后找比它大的数,找到后也挖出此数填到前一个坑a[j]中。

    4.再重复执行2,3二步,直到i==j,将基准数填入a[i]中。

    照着这个总结很容易实现挖坑填数的代码:

    int AdjustArray(int s[], int l, int r) //返回调整后基准数的位置
    {
    	int i = l, j = r;
    	int x = s[l]; //s[l]即s[i]就是第一个坑
    	while (i < j)
    	{
    		// 从右向左找小于x的数来填s[i]
    		while(i < j && s[j] >= x) 
    			j--;  
    		if(i < j) 
    		{
    			s[i] = s[j]; //将s[j]填到s[i]中,s[j]就形成了一个新的坑
    			i++;
    		}
    
    		// 从左向右找大于或等于x的数来填s[j]
    		while(i < j && s[i] < x)
    			i++;  
    		if(i < j) 
    		{
    			s[j] = s[i]; //将s[i]填到s[j]中,s[i]就形成了一个新的坑
    			j--;
    		}
    	}
    	//退出时,i等于j。将x填到这个坑中。
    	s[i] = x;
    
    	return i;
    }
    

    再写分治法的代码:

    void quick_sort1(int s[], int l, int r)
    {
    	if (l < r)
        {
    		int i = AdjustArray(s, l, r);//先成挖坑填数法调整s[]
    		quick_sort1(s, l, i - 1); // 递归调用 
    		quick_sort1(s, i + 1, r);
    	}
    }

    这样的代码显然不够简洁,对其组合整理下:

    //快速排序
    void quick_sort(int s[], int l, int r)
    {
        if (l < r)
        {
    		//Swap(s[l], s[(l + r) / 2]); //将中间的这个数和第一个数交换 参见注1
            int i = l, j = r, x = s[l];
            while (i < j)
            {
                while(i < j && s[j] >= x) // 从右向左找第一个小于x的数
    				j--;  
                if(i < j) 
    				s[i++] = s[j];
    			
                while(i < j && s[i] < x) // 从左向右找第一个大于等于x的数
    				i++;  
                if(i < j) 
    				s[j--] = s[i];
            }
            s[i] = x;
            quick_sort(s, l, i - 1); // 递归调用 
            quick_sort(s, i + 1, r);
        }
    }

    快速排序还有很多改进版本,如随机选择基准数,区间内数据较少时直接用另的方法排序以减小递归深度。有兴趣的筒子可以再深入的研究下。

     

    注1,有的书上是以中间的数作为基准数的,要实现这个方便非常方便,直接将中间的数和第一个数进行交换就可以了。

     

     转载请标明出处,原文地址:http://blog.csdn.net/morewindows/article/details/6684558

    展开全文
  • 快速排序算法

    2011-11-14 19:52:04
    快速排序算法快速排序算法快速排序算法快速排序算法快速排序算法
  • 快速排序算法 快速排序就是 递归调用此过程在以49为中点分割这个数据序列分别对前面一部分和后面一部分进行类似的快速排序从而完成全部数据序列的快速排序最后把此数据序列变成一个有序的序列根据这种思想对于上述 ...
  • 排序算法快速排序

    万次阅读 多人点赞 2018-04-24 22:02:57
    本文将介绍常见的排序算法中的“快速排序”。 基本思想 快速排序(QuickSort)是对冒泡排序的一种改进。快速排序由C. A. R. Hoare在1962年提出。它的基本思想是: 从要排序的数据中取一个数为“基准数”。 ...

    微信搜索【程序员囧辉】,关注这个坚持分享技术干货的程序员。

    我的最新文章:BAT 老兵的经验之谈,成长路上这个道理越早知道越好

    概述

    手写排序算法几乎是程序员面试必问的题目,大多数人都会选择写冒泡排序,如果此时你写的是其他改进过的排序算法,相信会让面试官眼前一亮。本文将介绍常见的排序算法中的“快速排序”。

     

    基本思想

    快速排序(QuickSort)是对冒泡排序的一种改进。快速排序由C. A. R. Hoare在1962年提出。它的基本思想是:

    1. 从要排序的数据中取一个数为“基准数”。
    2. 通过一趟排序将要排序的数据分割成独立的两部分,其中左边的数据都比“基准数”小,右边的数据都比“基准数”大。
    3. 然后再按步骤2对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。

    该思想可以概括为:挖坑填数 + 分治法。

     

    分治法

    分治,字面上的解释是“分而治之”,就是把一个复杂的问题分成两个或更多的相同或相似的子问题,再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解,原问题的解即子问题的解的合并。在计算机科学中,分治法就是运用分治思想的一种很重要的算法。分治法是很多高效算法的基础,如快速排序,归并排序,傅立叶变换(快速傅立叶变换)等等。

     

    例子

    下面通过一个例子来看看快速排序是怎么工作的,例子中表格中红色的字体为需要填的坑,绿色的字体为已经移动过的数据。

    1)刚开始,i 和 j 分别指向数组头和数组尾,即 i = 0,j = 9,基准数取第一个数,即 index = array[i] = array[0] = 23。

    此时,array[0] 的值已经存在了index,因此 array[0] 的位置就好像被挖了个坑,可以填充一个数。

    因此,我们从位置 j 开始向左寻找比 index 小的数,当 j = 8 时,符合条件,于是我们将 array[8] 的值填到 array[0] ,即将 9 填入 array[0],并将 i 向右移动一个位置,即 i++。

    从位置 j 向左寻找比 index 小的数,并在寻找到后填入坑中,用代码表示如下。

    while (i < j && array[j] >= index) { // 向左寻找第一个小于index的数
        j--;
    }
    if (i < j) {
        array[i++] = array[j]; // 将array[j]填入array[i],并将i向右移动
    }

    此时,array 数组如下图。

    2)因为 array[0] 的坑被 array[8] 填了,于是 array[8] 的位置又成了一个新的坑。此时我们从位置 i 开始向右寻找比 index 大的数,当 i = 2 时符合条件,于是我们将 array[2] 的值填到 array[8] ,即将 37 填入 array[8],并将 j 向左移动一个位置,即 j--。

    从位置 i 向右寻找比 index 大的数,并在寻找到后填入坑中,用代码表示如下(跟上面相似)。

    while (i < j && array[i] < index) {// 向右寻找第一个大于index的数
        i++;
    }
    if (i < j) {
        array[j--] = array[i]; // 将array[i]填入array[j],并将j向左移动
    }

    此时,array 数组如下图。

    以之后重复上述过程即可。

    3)同样的,array[8] 的坑被 array[2] 填了,于是 array[2] 的位置又成了一个新的坑。此时我们从位置 j 开始向左寻找比 index 小的数,当 j = 5 时符合条件,于是我们将 array[5] 的值填到 array[2] ,即将 21 填入 array[2],并将 i 向右移动一个位置,即 i++,此时 array 数组如下图。

    4)同样的,array[2] 的坑被 array[5] 填了,于是 array[5] 的位置又成了一个新的坑。此时我们从位置 i 开始向右寻找比 index 大的数,当 i = 3 时符合条件,于是我们将 array[3] 的值填到 array[5] ,即将 89 填入 array[5],并将 j 向左移动一个位置,即 j--,此时 array 数组如下图。

    5)同样的,array[5] 的坑被 array[3] 填了,于是 array[3] 的位置又成了一个新的坑。此时我们从位置 j 开始向左寻找比 index 小的数,当 j = 4 时符合条件,于是我们将 array[4] 的值填到 array[3] ,即将 2 填入 array[3],并将 i 向右移动一个位置,即 i++,此时 array 数组如下图。

    6)此时,我们发现 i = j,结束遍历,并将index填入 array[4],即将 23 填入 array[4],此时 array 数组如下图。此时,array[4] 左边的数据全比 array[4] 小,而 array[4] 右边的数据全比 array[4] 大。

    7)接下去,我们只需要对 array[4] 两边的数据分别在进行上面的操作即可(分治法),如下图。

    分治的代码可以写成如下:

    quickSort(array, low, i - 1); // 递归调用,分治
    quickSort(array, i + 1, high); // 递归调用,分治

     

    整合

    根据以上步骤,稍微整理一下,可以得出快速排序的代码如下:

    public class QuickSort {
        private static void quickSort(int[] array, int low, int high) {
            if (low >= high) {
                return;
            }
            int i = low, j = high, index = array[i]; // 取最左边的数作为基准数
            while (i < j) {
                while (i < j && array[j] >= index) { // 向左寻找第一个小于index的数
                    j--;
                }
                if (i < j) {
                    array[i++] = array[j]; // 将array[j]填入array[i],并将i向右移动
                }
                while (i < j && array[i] < index) {// 向右寻找第一个大于index的数
                    i++;
                }
                if (i < j) {
                    array[j--] = array[i]; // 将array[i]填入array[j],并将j向左移动
                }
            }
            array[i] = index; // 将基准数填入最后的坑
            quickSort(array, low, i - 1); // 递归调用,分治
            quickSort(array, i + 1, high); // 递归调用,分治
        }
    
        public static void quickSort(int[] array) {
            if (array == null || array.length == 0) {
                return;
            }
            quickSort(array, 0, array.length - 1);
        }
    }

     

    时间复杂度

    最好情况的时间复杂度为O(nlogn),过程比较复杂,就不在此赘述。

    最差情况下每一次取到的数(基准数)都是当前要比较的数中的最大/最小值,在这种情况下,每次都只能得到比上一次少1个数的子序列(即要么全比基准数大,要么全比基准小),此时相当于一个冒泡排序,比较的次数 = (n - 1) + (n - 2) + ... + 2 + 1 = (n - 1) * n / 2,此时的时间复杂度为:O(n^2)。最差情况一般出现在:待排序的数据本身已经是正序或反序排好了。

     

    使用场景

    基本上在任何需要排序的场景都可以使用快速排序。虽然快速排序的最坏情况时间复杂度为O(n^2),但是由于基本不会出现,因此可以放心的使用快速排序。在本人的电脑测试,100万的随机数字,快速排序大约耗时120毫秒。

     

    最后

    理解了快速排序的基本思想后,手写快速排序算法就变得没那么难了,只需要多练习几遍,相信在面试中手写快速排序算法便是小菜一碟。

     

    推荐阅读

     

    Java 基础高频面试题(2021年最新版)

    921天,咸鱼到阿里的修仙之路

    两年Java开发工作经验面试总结

    4 年 Java 经验,阿里网易拼多多面试总结、心得体会

    5 年 Java 经验,字节、美团、快手核心部门面试总结(真题解析)

     

    如何写一份让 HR 眼前一亮的简历(附模板)

    面试阿里,HashMap 这一篇就够了

    面试必问的 MySQL,你懂了吗?

    面试必问的线程池,你懂了吗?

    跳槽,如何选择一家公司

    如何准备好一场大厂面试

    MySQL 8.0 MVCC 核心原理解析(核心源码)

    复习2个月拿下美团offer,我都做了些啥

    展开全文
  • 快速排序算法——C/C++

    万次阅读 多人点赞 2019-06-12 22:55:14
    快速排序 1、算法思想 快速排序的基本思想:通过一趟排序将待排记录分隔成独立的两部分,其中一部分记录的关键字均比另一部分的关键字小,则可分别对这两部分记录继续进行排序,以达到整个序列有序。 2、实现原理 ...
  • 用C语言实现快速排序算法

    万次阅读 多人点赞 2016-11-04 22:33:13
    一、快速排序算法(Quicksort) 1. 定义 快速排序由C. A. R. Hoare在1962年提出。快速排序是对冒泡排序的一种改进,采用了一种分治的策略。 2. 基本思想 通过一趟排序将要排序的数据分割成独立的两部分,其中...
  • 今天被朋友问了个舍伍德排序算法,也是快速排序那种形式。尴尬,第一次听说,特意学了一下。结合快速排序,写了三个方法。 第一种: //不需要将基准值归位的快速排序 public static void quickSort(int []a,int ...
  • C++排序算法快速排序源码
  • 上个厕所的功夫,就学会了“快速排序算法

    万次阅读 多人点赞 2020-05-17 20:25:09
    快速排序由于排序效率在同为O(N*logN)的几种排序方法中效率较高,因此经常被采用,再加上快速排序思想----分治法也确实实用,因此很多软件公司的笔试面试,包括像BAT、TMD等知名IT公司都喜欢考查快速排序原理和手写...
  • 1、熟悉快速排序的串行算法 2、熟悉快速排序的并行算法 3、实现快速排序的并行算法 3.2 实验环境及软件 单台或联网的多台PC机,Linux操作系统,MPI系统。 3.3实验内容 1、快速排序的基本思想 2、单处理机上快速...
  • 易语言快速排序算法源码,快速排序算法,快速排序,KB
  • 排序算法系列:快速排序算法

    万次阅读 多人点赞 2016-03-01 15:40:07
     本文就来说说交换排序的最后一拍:快速排序算法。之所以说它是快速的原因,不是因为它比其他的排序算法都要快。而是从实践中证明了快速排序在平均性能上的确是比其他算法要快一些,不然快速一说岂不是在乱说?  ...
  • quick sort快速排序是一种再基础不过的排序算法,使用Python代码写起来相当简洁,这里我们就来看一下Python实现快速排序算法及去重的快速排序的简单示例:
  • 快速排序算法结构简单,平均性能较佳; 基数排序性能较稳定。结合快速排序和基数排序,本文提出超快速排序算法,通过理论分析和实验表明,新算法的性能优于快速排序算法和基数排序算法
  • C++排序算法快速排序
  • 理解快速排序算法的排序过程

    千次阅读 2018-01-28 13:06:43
    (2)排序算法的优点:好的快速排序算法在大多数计算机上运行得都比其他排序算法快,而且快速排序算法在空间上只使用一个小的辅助栈,其内部的循环也很小,另外快速排序算法也很容易实现,可以处理多种不同的输入...
  • 首先还是得简单的介绍一下快速排序这个算法快速排序(Quicksort),又称划分交换排序(partition-exchange sort),一种排序算法,最早由东尼·霍尔提出。在平均状况下,排序n个项目要Ο(n log n)次比较。在最坏...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 365,785
精华内容 146,314
关键字:

算法快速排序