快速排序 订阅
快速排序(Quicksort)是对冒泡排序的一种改进。 [1]  快速排序由C. A. R. Hoare在1960年提出。它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。 [1] 展开全文
快速排序(Quicksort)是对冒泡排序的一种改进。 [1]  快速排序由C. A. R. Hoare在1960年提出。它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。 [1]
信息
提出时间
1960年
别    称
快速排序
提出者
C. A. R. Hoare
应用学科
计算机科学
中文名
快速排序算法
适用领域范围
Pascal,c++等语言
外文名
quick sort
快速排序算法排序流程
快速排序算法通过多次比较和交换来实现排序,其排序流程如下: [2]  (1)首先设定一个分界值,通过该分界值将数组分成左右两部分。 [2]  (2)将大于或等于分界值的数据集中到数组右边,小于分界值的数据集中到数组的左边。此时,左边部分中各元素都小于或等于分界值,而右边部分中各元素都大于或等于分界值。 [2]  (3)然后,左边和右边的数据可以独立排序。对于左侧的数组数据,又可以取一个分界值,将该部分数据分成左右两部分,同样在左边放置较小值,右边放置较大值。右侧的数组数据也可以做类似处理。 [2]  (4)重复上述过程,可以看出,这是一个递归定义。通过递归将左侧部分排好序后,再递归排好右侧部分的顺序。当左、右两个部分各数据排序完成后,整个数组的排序也就完成了。 [2] 
收起全文
精华内容
下载资源
问答
  • 快速排序

    万次阅读 2020-04-24 01:10:08
    文章目录快速排序算法排序流程动图算法分析java代码 快速排序算法 快速排序是一种分治的排序算法,和冒泡排序同属于交换排序。 快速排序在每一轮都挑选一个基准元素,并让比它小的元素移到数列的一边,比它大的元素...

    快速排序算法

    快速排序是一种分治的排序算法,和冒泡排序同属于交换排序。

    快速排序在每一轮都挑选一个基准元素,并让比它小的元素移到数列的一边,比它大的元素移到数列数列的另一边,从而把数列拆分成两部分。

    排序流程

    1. 从数列中挑出一个基准元素(pivot);
    2. 所有比基准值小的元素移动到基准前面,其它比基准值大的元素移到基准的后面(相同的数可以不动)。完成后该基准就处于数列的中间位置,称为分区操作;
    3. 递归地把小于基准值元素的子数列和大于基准值元素的子数列排序。

    动图

    image

    算法分析

    快速排序算法的效率在序列越乱的时候,效率越高,在数据有序时,会退化成冒泡排序。

    优点:极快数据移动少。

    缺点:不稳定。

    最佳情况:O(nlogn)
    
    最差情况:O(n^2)
    
    平均情况:O(nlogn)
    
    空间复杂度:O(nlogn)
    

    java代码

    @Override
    public <T extends Comparable<T>> T[] sort(T[] array) {
        doSort(array, 0, array.length - 1);
        return array;
    }
    
    private static <T extends Comparable<T>> void doSort(T[] array, int left, int right) {
        if (left < right) {
            int pivot = randomPartition(array, left, right);
            doSort(array, left, pivot - 1);
            doSort(array, pivot, right);
        }
    }
    
    private static <T extends Comparable<T>> int randomPartition(T[] array, int left, int right) {
        int randomIndex = left + (int)(Math.random()*(right - left + 1));
        swap(array, randomIndex, right);
        return partition(array, left, right);
    }
    
    private static <T extends Comparable<T>> int partition(T[] array, int left, int right) {
        int mid = (left + right) / 2;
        T pivot = array[mid];
    
        while (left <= right) {
            while (less(array[left], pivot)) {
                ++left;
            }
            while (less(pivot, array[right])) {
                --right;
            }
            if (left <= right) {
                swap(array, left, right);
                ++left;
                --right;
            }
        }
        return left;
    }
    
    展开全文
  • 快速排序---(面试碰到过好几次)

    万次阅读 多人点赞 2018-09-10 12:20:21
       快速排序,说白了就是给基准数据找其正确索引位置的过程.    如下图所示,假设最开始的基准数据为数组第一个元素23,则首先用一个临时变量去存储基准数据,即tmp=23;然后分别从数组的两端扫描数组,设两个指示...

    原理:

       快速排序,说白了就是给基准数据找其正确索引位置的过程.
       如下图所示,假设最开始的基准数据为数组第一个元素23,则首先用一个临时变量去存储基准数据,即tmp=23;然后分别从数组的两端扫描数组,设两个指示标志:low指向起始位置,high指向末尾.
    这里写图片描述
       首先从后半部分开始,如果扫描到的值大于基准数据就让high减1,如果发现有元素比该基准数据的值小(如上图中18<=tmp),就将high位置的值赋值给low位置 ,结果如下:
    这里写图片描述
    然后开始从前往后扫描,如果扫描到的值小于基准数据就让low加1,如果发现有元素大于基准数据的值(如上图46=>tmp),就再将low位置的值赋值给high位置的值,指针移动并且数据交换后的结果如下:
    这里写图片描述
    然后再开始从后向前扫描,原理同上,发现上图11<=tmp,则将low位置的值赋值给high位置的值 ,结果如下:
    然后再开始从后向前扫描,原理同上,发现上图11<=tmp,则将high位置的值赋值给low位置的值,结果如下:
    这里写图片描述
    然后再开始从前往后遍历,直到low=high结束循环,此时low或high的下标就是基准数据23在该数组中的正确索引位置.如下图所示.
    这里写图片描述
      这样一遍走下来,可以很清楚的知道,其实快速排序的本质就是把基准数大的都放在基准数的右边,把比基准数小的放在基准数的左边,这样就找到了该数据在数组中的正确位置.
      以后采用递归的方式分别对前半部分和后半部分排序,当前半部分和后半部分均有序时该数组就自然有序了。

    一些小结论

    从上面的过程中可以看到:

      ①先从队尾开始向前扫描且当low < high时,如果a[high] > tmp,则high–,但如果a[high] < tmp,则将high的值赋值给low,即arr[low] = a[high],同时要转换数组扫描的方式,即需要从队首开始向队尾进行扫描了
      ②同理,当从队首开始向队尾进行扫描时,如果a[low] < tmp,则low++,但如果a[low] > tmp了,则就需要将low位置的值赋值给high位置,即arr[low] = arr[high],同时将数组扫描方式换为由队尾向队首进行扫描.
      ③不断重复①和②,知道low>=high时(其实是low=high),low或high的位置就是该基准数据在数组中的正确索引位置.

    按照上诉理论我写的代码如下:

    package com.nrsc.sort;
    
    public class QuickSort {
    	public static void main(String[] args) {
    		int[] arr = { 49, 38, 65, 97, 23, 22, 76, 1, 5, 8, 2, 0, -1, 22 };
    		quickSort(arr, 0, arr.length - 1);
    		System.out.println("排序后:");
    		for (int i : arr) {
    			System.out.println(i);
    		}
    	}
    
    	private static void quickSort(int[] arr, int low, int high) {
    
    		if (low < high) {
    			// 找寻基准数据的正确索引
    			int index = getIndex(arr, low, high);
    
    			// 进行迭代对index之前和之后的数组进行相同的操作使整个数组变成有序
    			//quickSort(arr, 0, index - 1); 之前的版本,这种姿势有很大的性能问题,谢谢大家的建议
    			quickSort(arr, low, index - 1);
    			quickSort(arr, index + 1, high);
    		}
    
    	}
    
    	private static int getIndex(int[] arr, int low, int high) {
    		// 基准数据
    		int tmp = arr[low];
    		while (low < high) {
    			// 当队尾的元素大于等于基准数据时,向前挪动high指针
    			while (low < high && arr[high] >= tmp) {
    				high--;
    			}
    			// 如果队尾元素小于tmp了,需要将其赋值给low
    			arr[low] = arr[high];
    			// 当队首元素小于等于tmp时,向前挪动low指针
    			while (low < high && arr[low] <= tmp) {
    				low++;
    			}
    			// 当队首元素大于tmp时,需要将其赋值给high
    			arr[high] = arr[low];
    
    		}
    		// 跳出循环时low和high相等,此时的low或high就是tmp的正确索引位置
    		// 由原理部分可以很清楚的知道low位置的值并不是tmp,所以需要将tmp赋值给arr[low]
    		arr[low] = tmp;
    		return low; // 返回tmp的正确位置
    	}
    }
    
    
    展开全文
  • 快速排序(过程图解)

    万次阅读 多人点赞 2018-07-02 12:10:50
    假设我们现在对“612 79345 108”这个10个数进行排序。首先在这个序列中随便找一个数作为基准数(不要被这个名词吓到了,就是一个用来参照的数,待会你就知道它用来做啥的了)。为了方便,就让第一个数6作为基准数吧...
    假设我们现在对“6  1  2 7  9  3  4  5 10  8”这个10个数进行排序。首先在这个序列中随便找一个数作为基准数(不要被这个名词吓到了,就是一个用来参照的数,待会你就知道它用来做啥的了)。为了方便,就让第一个数6作为基准数吧。接下来,需要将这个序列中所有比基准数大的数放在6的右边,比基准数小的数放在6的左边,类似下面这种排列。
           3  1  2 5  4  6  9 7  10  8
     
            在初始状态下,数字6在序列的第1位。我们的目标是将6挪到序列中间的某个位置,假设这个位置是k。现在就需要寻找这个k,并且以第k位为分界点,左边的数都小于等于6,右边的数都大于等于6。想一想,你有办法可以做到这点吗?
     
            给你一个提示吧。请回忆一下冒泡排序,是如何通过“交换”,一步步让每个数归位的。此时你也可以通过“交换”的方法来达到目的。具体是如何一步步交换呢?怎样交换才既方便又节省时间呢?先别急着往下看,拿出笔来,在纸上画画看。我高中时第一次学习冒泡排序算法的时候,就觉得冒泡排序很浪费时间,每次都只能对相邻的两个数进行比较,这显然太不合理了。于是我就想了一个办法,后来才知道原来这就是“快速排序”,请允许我小小的自恋一下(^o^)。
     
           方法其实很简单:分别从初始序列“6  1  2 7  9  3  4  5 10  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要大,满足要求)之后停了下来。此时再次进行交换,交换之后的序列如下。
            6  1  2 5  4  3  9  7 10  8
     
            第二次交换结束,“探测”继续。哨兵j继续向左挪动,他发现了3(比基准数6要小,满足要求)之后又停了下来。哨兵i继续向右移动,糟啦!此时哨兵i和哨兵j相遇了,哨兵i和哨兵j都走到3面前。说明此时“探测”结束。我们将基准数6和3进行交换。交换之后的序列如下。
            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”。请将这个序列以3为基准数进行调整,使得3左边的数都小于等于3,3右边的数都大于等于3。好了开始动笔吧。
     
            如果你模拟的没有错,调整完毕之后的序列的顺序应该是。
            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)。
    #include <stdio.h>
    int a[101],n;//定义全局变量,这两个变量需要在子函数中使用
    void quicksort(int left, int right) {
    	int i, j, t, temp;
    	if(left > right)
    		return;
        temp = a[left]; //temp中存的就是基准数
        i = left;
        j = right;
        while(i != j) { //顺序很重要,要先从右边开始找
        	while(a[j] >= temp && i < j)
        		j--;
        	while(a[i] <= temp && i < j)//再找右边的
        		i++;       
        	if(i < j)//交换两个数在数组中的位置
        	{
        		t = a[i];
        		a[i] = a[j];
        		a[j] = t;
        	}
        }
        //最终将基准数归位
        a[left] = a[i];
        a[i] = temp;
        quicksort(left, i-1);//继续处理左边的,这里是一个递归的过程
        quicksort(i+1, right);//继续处理右边的 ,这里是一个递归的过程
    }
    int main() {
    	int i;
        //读入数据
    	scanf("%d", &n);
    	for(i = 1; i <= n; i++)
    		scanf("%d", &a[i]);
        quicksort(1, n); //快速排序调用
        //输出排序后的结果
        for(i = 1; i < n; i++)
        	printf("%d ", a[i]);
        printf("%d\n", a[n]);
        return 0;
    }

     

     
    展开全文
  • 快速排序基本思路(通俗易懂+例子)

    万次阅读 多人点赞 2017-07-02 22:06:32
    快速排序今天看到大神写的一篇快速排序的博客,肃然起敬,觉得原来快速排序这么简单 下面进行简单的试试快速排序的基本思想是 1、先从数列中取出一个数作为基准数 2、分区过程,将比这个数大的数全放到它的...

    快速排序

    今天看到大神写的一篇快速排序的博客,肃然起敬,觉得原来快速排序这么简单
    下面进行简单的试试

    快速排序的基本思想是

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

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

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

    概括来说为 挖坑填数+分治法

    下面举例来进行说明,主要有三个参数,i为区间的开始地址,j为区间的结束地址,X为当前的开始的值

    第一步,i=0,j=9,X=21

    0 1 2 3 4 5 6 7 8 9
    21 32 43 98 54 45 23 4 66 86

    第二步,从j开始由,后向前找,找到比X小的第一个数a[7]=4,此时i=0,j=6,X=21
    进行替换

    0 1 2 3 4 5 6 7 8 9
    4 32 43 98 54 45 23 21 66 86

    第三步,由前往后找,找到比X大的第一个数a[1]=32,此时i=2,j=6,X=21

    0 1 2 3 4 5 6 7 8 9
    4 21 43 98 54 45 23 32 66 86

    第四步,从j=6开始由,由后向前找,找到比X小的第一个数a[0]=4,此时i=2,j=0,X=21,发现j<=i,所以第一回结束

    可以发现21前面的数字都比21小,后面的数字都比21大
    接下来对两个子区间[0,0]和[2,9]重复上面的操作即可

    下面直接给出过程,就步详细解说了

    i=2,j=6,X=43

    0 1 2 3 4 5 6 7 8 9
    4 21 43 98 54 45 23 32 66 86

    i=4,j=6,X=43

    0 1 2 3 4 5 6 7 8 9
    4 21 32 98 54 45 23 43 66 86

    i=4,j=5,x=43

    0 1 2 3 4 5 6 7 8 9
    4 21 32 43 54 45 23 98 66 86

    i=5,j=5,x=43

    0 1 2 3 4 5 6 7 8 9
    4 21 32 23 43 45 54 98 66 86

    然后被分为了两个子区间[2,3]和[5,9]

    …最后排序下去就是最终的答案

    0 1 2 3 4 5 6 7 8 9
    4 21 23 32 43 45 54 66 86 98

    总结:

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

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

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

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


    代码

    class Solution {
    	public void sort(int left,int right,int[] array) {
    		if (left>=right) return ;
    		int start=left;
    		int end=right;
    		int flag=left;
    		while(left<right) {
    			while ((left<right)&&(array[right]>=array[flag])) {
    				right--;
    			}
    			if (array[right]<array[flag]) {
    				int tmp=array[right];
    				array[right]=array[flag];
    				array[flag]=tmp;
    				flag=right;
    			}
    			while ((left<right)&&(array[left]<=array[flag])) {
    				left++;
    				}
    			if (array[left]>array[flag]) {
    				int tmp=array[left];
    				array[left]=array[flag];
    				array[flag]=tmp;
    				flag=left;
    			}
    		}
    		sort(start, left-1, array);
    		sort(left+1, end, array);
    	}
    }
    

    分享一个比较牛逼的学习java的网站,基础知识和架构等都有,连接如下:
    http://how2j.cn?p=54321
    在这里插入图片描述

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

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

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

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

    万次阅读 多人点赞 2020-05-17 20:25:09
    快速排序由于排序效率在同为O(N*logN)的几种排序方法中效率较高,因此经常被采用,再加上快速排序思想----分治法也确实实用,因此很多软件公司的笔试面试,包括像BAT、TMD等知名IT公司都喜欢考查快速排序原理和手写...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 80,080
精华内容 32,032
关键字:

快速排序