精华内容
下载资源
问答
  • 2014-09-13 23:35:37
    #include<iostream>
    using namespace std;
    
    const int M = 20;
    void quickSort(int *data,const int left,const int right);
    int partition(int *data,const int low,const int high);
    void insertSort(int *data,const int left,const int right);
    void swap(int &a,int &b);
    int main()
    {
    	int size = 0;
    	cin >> size;
    	if (size > 100 || size < 1)
    		return 0;
    	int *data = new int[size];
    	for (int i = 0; i < size; ++i)
    		cin >> data[i];
    
    	quickSort(data,0,size-1);
    	for (int i = 0; i < size; ++i)
    		cout << data[i] << " ";
    
    	return 0;
    }
    
    void quickSort(int *data, const int left, const int right)
    {
    	if (right - left < M)
    		insertSort(data,left,right);
    	//if (right <= left)
    		//return;
    	else
    	{
    		int pivotPos = partition(data,left,right);
    		quickSort(data,left,pivotPos-1);
    		quickSort(data,pivotPos+1,right);
    	}
    }
    
    int partition(int *data, const int low, const int high)
    {
    	int pivotPos = low;
    	int pivotValue = data[low];
    	for (int i = low+1; i <= high; ++i)
    	{
    		if (pivotPos == i)
    			continue;
    		if (pivotValue > data[i])
    		{
    			swap(data[++pivotPos], data[i]);
    		}
    	}
    	data[low] = data[pivotPos];
    	data[pivotPos] = pivotValue;
    	return pivotPos;
    }
    
    void swap(int &a, int &b)
    {
    	int temp = a;
    	a = b;
    	b = temp;
    }
    
    void insertSort(int *data, const  int left, const int right)
    {
    	int current = 0;
    	for (int i = left+1; i <= right; ++i)
    	{
    		current = data[i];
    		int j;
    		for (j = i-1; j >=left; --j)
    		{
    			if (current < data[j])
    			{
    				data[j + 1] = data[j];
    			}
    			else
    			{
    				break;
    			}
    		}
    		data[j+1] = current;
    	}
    }



    对于长度比较小的序列,快排并不比简单的排序算法快,因此加了一个插入排序(当序列长度小于20时用插入排序)。

    研究表明,序列长度取值为5——25时,采用直接插入排序要比快排至少快10%。



    更多相关内容
  • 主要为大家详细介绍了C语言实现快速排序改进代码,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
  • 代码中包含了快速排序这个经典算法的代码,并且给出了改进后的快速排序的代码,代码中同时包含了两个测试用例。测试命令:g++ quicksort.cpp -o quicksort ./quicksork
  • 文章目录快速排序思路注意!!!!!错误代码正确代码代码优化 快速排序 思路 如果列表为空或者只有一个元素则不用排序 选择首元素为基准值 创建两个列表:小于基准值的less=[ ]和大于基准值的high=[ ] 遍历整个列表...
  • 快速排序改进

    2018-06-25 15:34:08
    快速排序法基础上提供了一些改进,比基本的快速排序更方便简洁
  • 快速排序算法改进--小的子文件、三者取中、重复关键字三路划分
  • 快速排序改进优化

    千次阅读 2018-03-20 22:46:43
    以前写的快速排序,基本上按下面伪代码这个套路写出来就完了,但其实对于快排,可以通过很多方面来进行改进以达到更好的效率。 algorithm quicksort(A, lo, hi) is if lo &lt; hi then p := partition(A, ...

    以前写的快速排序,基本上按下面伪代码这个套路写出来就完了,但其实对于快排,可以通过很多方面来进行改进以达到更好的效率。

    algorithm quicksort(A, lo, hi) is
        if lo < hi then
            p := partition(A, lo, hi)
            quicksort(A, lo, p)
            quicksort(A, p + 1, hi)
    
    algorithm partition(A, lo, hi) is
        pivot := A[lo]
        i := lo - 1
        j := hi + 1
        loop forever
            do
                i := i + 1
            while A[i] < pivot
    
            do
                j := j - 1
            while A[j] > pivot
    
            if i >= j then
                return j
    
            swap A[i] with A[j]

    快排模拟
    先回顾一下上面快排的模拟图
    分析:

    • 首先,清楚快排原理的同志都知道,快排特别热衷于凌乱的数据,最好情况下时间复杂度能达到O(nlogn),空间复杂度为O(logn);但是对于基本有序或者倒序的数据则无能为力,时间复杂度直接降到O(n^2),空间复杂度为O( n ) 。对于这种情况,取一个合理的基准值就很重要了。
      一种较为稳妥的方法是随机选取数组中的某个位置,而不是总是顽固地选择最右端的元素,这样确实可以避免排序的退化。
      再回想我们为什么要取随机值?就是为了避免输入数据有序造成的异常,如果一种方法能够在这种情况下利用这种原有的有序性岂不是更好吗?三值取中法就是这样的方法,它的选取方法是先从数组的开头、结尾和中间选取3个元素,再取这3个元素的中间值作为划分的基准。首先,三值取中法本身带有一定的随机性,所以能够很好的处理随机数据;其次,它使得最坏情况几乎不可能发生,如果数组原本就具有有序性,那么按照原始的划分方法,取到的3个元素中必然有2个将被划分到大于(或小于)v的值所在的数组中,而三值取中法则扭转了这种不利;最后,与随机化方法相比,三值取中法省去了生成随机数的开销。
    • 其次,在快速排序算法的递归实现中,存在一种不太好的现象:随着递归层层深入,大量数据被分割成了小数组;快排对于大数组的划分可以迅速地将元素移动到它正确位置的附近,比如说对1024进行一次均等划分,那么某个元素可能会移动数百个单位位置,若进行4次均等划分,元素在正确位置上的概率就从1/1024骤升到1/64,考虑到64与1024的绝对数值,这是相当高的效率;然而对于小数组,快速排序的效率就不那么理想了,对于16个元素的数组,快速排序也要划分4次才能把它移动到正确的位置上,相对于之前几百个位置的移动,小数组排序一次只能移动几个单位的位置。
      换句话说,快速排序对少量数据的划分远不如它对大量数据的划分这么划算,当排序进入到小数组阶段后,它将多次因为这些小数组而频繁调用自身,但获得的收益并不大,我姑且把这种现象叫做小数组的边际效益。采取分治递归策略的排序算法(如归并排序)都存在同样的问题,所以这类排序都可以在这方面优化。对大量数据排序时,我们应该在前期利用快速排序的特点,让这些数据迅速移动到正确位置附近,然后在后期消除小数组的边际效应。
      消除边际效应的一个方法就是设定一个M值,当数组元素个数小于M时,视为小数组,此时快速排序就直接返回,最后把数组处理得差不多时,再用其它排序方法对数组进行最终排序。那么M值应该取多少?又应该选择何种排序算法进行最终排序?
      首先回答第二个问题,因为它的答案是显而易见的。对接近有序的数据排序,没有什么算法比插入排序更合适了,插入排序的执行开销与所有元素偏离自己正确位置的距离成正比。

    最后看一下结合上面两种改进方法写出来的快排:

    package sort;
    
    public class QuickSortDemo2 {
        private static void print(long[] a) {
            System.out.print("a : ");
            for (int i = 0; i < a.length; i++) {
                System.out.print(a[i] + " ");
            }
            System.out.println();
        }
    
        private static void quickSort(long[] a, int left, int right) {
    //      if(right<=left){
    //          return;
    //      }
            //当数组长度比较短并且基本有序时,使用插入排序会有比较好的效率提升
            if (right - left + 1 <= 10) {
                insertSort(a, left, right);
            } else {
                //取left和right的中间值,有两个好处:1、防止对于基本有序的数组进行多余无效的交换;2、能够很巧妙的为数组越界作参考标准
                long median = getMedian(a, left, right);
                int partition = partitionInt(a, left, right, median);
                quickSort(a, left, partition-1);
                quickSort(a, partition+1, right);
            }
        }
    
        private static int partitionInt(long[] a, int left, int right, long median) {
            int leftPtr = left;
            int rightPtr = right - 1;
            while (true) {
                while (a[++leftPtr] < median)   //因为median取的是left、right和center的中间值,所以仅通过一句判断很巧妙的实现了数组越界的判断
                    ;
                while (a[--rightPtr] > median)  //同上
                    ;
                if(leftPtr >= rightPtr){
                    break;
                }
                swap(a,leftPtr,rightPtr);
            }
            swap(a, leftPtr, right-1);
            return leftPtr;
        }
    
        private static long getMedian(long[] a, int left, int right) {
            int center = (left + right) / 2;
            if (a[left] > a[center]) {
                swap(a, left, center);
            }
            if (a[left] > a[right]) {
                swap(a, left, right);
            }
            if (a[center] > a[right]) {
                swap(a, center, right);
            }
            swap(a, center, right - 1); //将中值放到right-1位置,后面的比较替换只针对left+1~right-2
            return a[right - 1];
        }
    
        private static void insertSort(long[] a, int left, int right) {
            int in, out;
            for (out = left + 1; out <= right; out++) {
                in = out;
                long temp = a[out];
                while (in > left && a[in - 1] > temp) {
                    a[in] = a[in - 1];
                    --in;
                }
                a[in] = temp;
            }
    
        }
    
        private static void swap(long[] a, int i, int j) {
            long temp = a[i];
            a[i] = a[j];
            a[j] = temp;
        }
    
        public static void main(String[] args) {
            long[] a = new long[10000];
            for (int i = 0; i < a.length; i++) {
                a[i] = (long) (Math.random() * 99);
            }
            print(a);
            long startTime = System.currentTimeMillis();
            quickSort(a, 0, a.length - 1);
            long endTime = System.currentTimeMillis();
            System.out.println("use: " + (endTime - startTime) + "ms");
            print(a);
    
        }
    
    }
    
    

    github:
    https://github.com/aweneves/Algorithm1/blob/master/src/sort/QuickSortDemo2.java

    展开全文
  • 快速排序改进

    2016-03-30 22:05:01
    快速排序平均复杂度为O(nlgn), 最坏情况为O(n^2),即数组已经有序或大致有序的情况下,每次划分只能减少一个元素,快速排序将不幸退化为冒泡排序,所以快速排序时间复杂度下界为O(nlogn),最坏情况下为O(n^2) 1....

    快速排序平均复杂度为O(nlgn)

    最坏情况为O(n^2)即数组已经有序或大致有序的情况下,每次划分只能减少一个元素,快速排序将不幸退化为冒泡排序,所以快速排序时间复杂度下界为O(nlogn),最坏情况下为O(n^2)

    1.如果在排序时选取最后一个元素为基准,则可以通过以下方法来避免划分的不平衡。

    int Patition(int *pnArr, int nLeft, int nRight)
    {
        int nKey = nRight;
        int i = nLeft - 1;
        bool bExchange = false;
    
        for (int j = nLeft; j < nRight; j++)
        {
            if (pnArr[j] < pnArr[nKey])
            {
                i++;
                Swap(&pnArr[i], &pnArr[j]);
                bExchange = true;
            }
        }
        Swap(&pnArr[i+1],&pnArr[nRight]);
        if (bExchange)
        {
            return i+1;
        }
        else
        {
            return (nLeft + nRight) / 2;
        }
    }

    即设置一个标志标示在划分过程中有没有交换元素,如果没有交换元素就返回数组中间的元素,这样就可以避免最坏情况。

    2.但是上面的改进只适合选取最后一个元素,如果对于一个有序序列,选取中间元素为基准,则把中间的元素交换到最后还是会又一次交换的过程,不能改善。(改善方法可以同下面的随机选取元素方法一样设置阈值).

    3.快速排序的最坏情况基于每次划分对基准元素的选择。基本的快速排序选取第一个元素作为基准元素。这样在数组已经有序的情况下,每次划分将得到最坏的结果。一种比较常见的优化方法是随机化算法,即随机选取一个元素作为基准元素。这种情况下虽然最坏情况仍然是O(n^2),但最坏情况不再依赖于输入数据,而是由于随机函数取值不佳。实际上,随机化快速排序得到理论最坏情况的可能性仅为1/(2^n)。所以随机化快速排序可以对于绝大多数输入数据达到O(nlogn)的期望时间复杂度。

    4.设置阈值。快速排序的实现需要消耗递归栈的空间,而大多数情况下都会通过使用系统递归栈来完成递归求解。在元素数量较大时,对系统栈的频繁存取会影响到排序的效率。

    一种常见的办法是设置一个阈值,在每次递归求解中,如果元素总数不足这个阈值,则放弃快速排序,调用一个简单的排序过程完成该子序列的排序。这样的方法减少了对系统递归栈的频繁存取,节省了时间的消费。

    一般的经验表明,阈值取一个较小的值,排序算法采用选择、插入等紧凑、简洁的排序。一个可以参考的具体方案:阈值T=10,排序算法用选择排序。阈值不要太大,否则省下的存取系统栈的时间,将会被简单排序算法较多的时间花费所抵消。

    展开全文
  • 取首尾元素的值的平均值作为比较,是快速排序改进算法
  • 快速排序改进

    千次阅读 2018-07-30 00:02:48
    快速排序基本思路:找到一个标定点,左边的元素小于标定点,右边元素大于标定点,然后再对左右区间递归快速排序。 // 对arr[l...r]部分进行partition操作 // 返回p, 使得arr[l...p-1] &lt; arr[p] ; arr[p+1.....

    快速排序基本思路:找到一个标定点,左边的元素小于标定点,右边元素大于标定点,然后再对左右区间递归快速排序。

    // 对arr[l...r]部分进行partition操作
    // 返回p, 使得arr[l...p-1] < arr[p] ; arr[p+1...r] > arr[p]
    template <typename T>
    int __partition(T arr[], int l, int r) {
    
    	T v = arr[l];
    
    	int j = l; // arr[l+1...j] < v ; arr[j+1...i) > v
    	for (int i = l + 1; i <= r; i++)
    		if (arr[i] < v) {
    			j++;
    			swap(arr[j], arr[i]);
    		}
    
    	swap(arr[l], arr[j]);
    
    	return j;
    }
    
    // 对arr[l...r]部分进行快速排序
    template <typename T>
    void __quickSort(T arr[], int l, int r) {
    
    	if (l >= r)
    		return;
    
    	int p = __partition(arr, l, r);
    	__quickSort(arr, l, p - 1);
    	__quickSort(arr, p + 1, r);
    }
    
    template <typename T>
    void quickSort(T arr[], int n) {
    
    	__quickSort(arr, 0, n - 1);
    }

    改进1:如果数组近乎有序,标定点的选择会影响快速排序的性能,如果每次都选择最小值作为标定点,快速排序时间复杂度会退化为O(n^{2}),因此需要随机化标定点元素。

    template <typename T>
    int __partition(T arr[], int l, int r) {
    	// 随机在arr[l...r]的范围中, 选择一个数值作为标定点pivot
    	swap(arr[l], arr[rand() % (r - l + 1) + l]);
    	T v = arr[l];
    
    	int j = l; // arr[l+1...j] < v ; arr[j+1...i) > v
    	for (int i = l + 1; i <= r; i++)
    		if (arr[i] < v) {
    			j++;
    			swap(arr[j], arr[i]);
    		}
    
    	swap(arr[l], arr[j]);
    
    	return j;
    }

    改进2:如果数组有大量相同元素,上面的做法会将相同元素分到大于v的区间,会造成两个子区间元素不平衡,所以需要将相等元素平衡地分入两个区间。

    template <typename T>
    int _partition2(T arr[], int l, int r) {
    
    	// 随机在arr[l...r]的范围中, 选择一个数值作为标定点pivot
    	swap(arr[l], arr[rand() % (r - l + 1) + l]);
    	T v = arr[l];
    	
    	//[l+1,i) <=v, (j,r]>=v
    	int i = l + 1, j = r;
    	while (i <j)
    	{
    		while (i <=r&&arr[i] < v)
    			i++;
    		while (j >l && arr[j-1] > v)
    			j--;
    		swap(arr[i], arr[j]);
    		i++; j--;
    	}
    	swap(arr[i], arr[l]);
    	return i;
    }

    对应地,还有三路快速排序算法。

    展开全文
  • 快速排序 改进快排的方法

    万次阅读 2013-10-07 11:32:42
    快速排序法事应用最广泛的排序算法之一,最佳情况下时间复杂度是 O(nlogn)。但是最坏情况下可能达到O(n^2)。说明快速排序达到最坏情况的原因。并提出改善方案并实现之。 答: 改进方案:改进选取枢轴的方法 1、...
  • 文章目录公共函数快速排序第一版快速排序改进1.阈值选取2.优化不必要的交换3.优化小数组的排序4.优化递归操作完整代码 快速排序的主要思想就是”分而治之“。 对于快速排序而言,”分而治之“的意思是将数组拆分为...
  • 本资源包含快排(Quicksort)桶排序(BucketSort)三数取中快速排序(middle、partition、QuickSort3)及三数取中+同key值相聚快速排序(middle1、QuickSort4)。可见三数取中+同key相聚算法还是很猛的!
  • 这是简单的快速排序和加入各种改进算法的后的代码都有,比如快排入栈操作等
  • 【排序算法】快速排序的分析改进

    千次阅读 2018-03-19 17:24:17
    基本的快速排序最基本的快速排序是由C.A.R.Hoare在1960年提出的,快速排序的算法是一种分治排序算法它将数组划分为两个部分,然后分别对两个部分进行排序快速每次对数组重新排序,选择一个基准值key,然后让数组满足...
  • 快速排序是冒泡排序经改进之后的一种新的排序方法。拥有速度快,原地排序等特点,本文主要探讨了对原始的快速排序的一些改进的想法,提高其效率。
  • 快速排序及其改进算法C++实现

    千次阅读 2016-05-10 16:18:00
    快速排序可以看成是插入排序的改进,它与插入排序的不同在与:快速排序是将控制划分过程的关键词直接放在最终的位置,而不是放在合适的位置。思想是:对于元素Ki将其放在最终的位置(即左边所有的元素都小于它,右边...
  • 冒泡排序到快速排序做的那些优化

    千次阅读 2017-10-28 07:39:51
    彻底弄明白常用的排序算法的基本思想,算法的时间和空间复杂度,以及如何选择这些排序算法,确定要解决的问题的最佳排序算法,我们先总结下冒泡排序和其改进后的快速排序这两个算法,后面再继续总结插入排序、希尔...
  • 快速排序及优化方案

    千次阅读 2022-02-20 18:31:36
    文章目录快速排序及其优化方案1. 快速排序的流程2. 快速排序的实现时间复杂度计算3. 快速排序优化随机获取基准值进行优化3.2二路快速排序原理:思想:4. 总结 快速排序及其优化方案 1. 快速排序的流程 首先设定一个...
  • 针对快速排序在某些特殊情况下如数据已有序或重复数据较多时效率较低的问题进行了研究, 对三路快速排序进行改进, 使快速排序在特殊情况下也能保持较好的效率。通过大量的数据测试发现, 该算法在最好情况下其性能在几...
  • 1、 时间复杂度: 最好情况:o(n); 平均情况:o(nlogn) ... (3)递归对步骤二的两个子数列再次进行排序; (4)终止条件:子数列的长度是1时结束。 3、优化策略(主要从基准值的选择、减...
  • 快速排序算法图解分析

    千次阅读 2020-10-21 17:21:12
    1.快速排序是对冒泡排序的改进。冒泡排序每次交换只能使原序列的逆序数减一(相邻元素的交换),而快速排序可以进行不相邻元素的交换,逆序数至少减少1。(当排序序列逆序数为0时,排序就完成了) 百度百科的逆序数...
  • 主要为大家详细介绍了C++实现快速排序(Quicksort)算法,文中示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
  • 改进快速排序算法

    2013-11-04 14:58:06
    快速排序算法的改进思路 1.选取好的基准,是两边的数据个数尽量的均匀 取数组的第一个,中间,最后一个数据,取三个数中第二大的数作为基准 2. 不递归 3.与插入结合,当段内的数组个数小于等于16的时候,使用...
  • 快速排序 对冒泡排序的一种改进,若初始记录序列按关键字有序或基本有序,蜕化为冒泡排序。使用的是递归原理,在所有同数量级O(n longn) 的排序方法中,其平均性能最好。就平均时间而言,是目前被认为最好的一种内部...
  • 快速排序(QuickSort)是对冒泡排序的一种改进: 基本思想: 通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序...
  • 直接插入排序、希尔排序、直接选择排序、堆排序、冒泡排序、快速排序、归并排序、基数排序。 算法复杂度比较: 算法分类 一、直接插入排序 一个插入排序是另一种简单排序,它的思路是:每次从未排好的序列中选出第一...
  • 快速排序算法的改进与分析.doc
  • 快速排序是对冒泡排序的一种改进,采用了一种分治的策略。 2. 基本思想 通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 93,947
精华内容 37,578
关键字:

快速排序改进

友情链接: nginx-1.16.0.zip