精华内容
下载资源
问答
  • 快速排序非递归实现

    2015-11-29 11:09:07
    再来谈谈快速排序,递归实现与非递归实现。 递归实现是基本的排序;非递归实现需要用stack来存储 (low, high)的排序对,一部分一部分的排序。 直接上程序了: 头文件 quick_test.h#include #include #include ...

    再来谈谈快速排序,递归实现与非递归实现。
    递归实现是基本的排序;非递归实现需要用stack来存储 (low, high)的排序对,一部分一部分的排序。
    直接上程序了:
    头文件 quick_test.h

    #include <stdio.h>
    #include <stdlib.h>
    #include <time.h>
    #include <sys/time.h>
    
    /
    #include <stack>
    #include <iostream>
    typedef struct REGION{
        long low;
        long high;
    } Region;
    ///
    
    //#define N 100000000
    #define N 15
    //#define M 1000000000
    #define M 1000
    
    typedef long Data;
    
    void SwpData(Data &data1, Data &data2);
    
    void quickSort(Data *arr, long low, long high);
    
    long partition(Data *arr, long low, long high);
    
    void quickSortNew(Data *arr, long low, long high);

    简单的排序主函数,quick_test.cpp

    #include "quick_test.h"
    
    void SwpData(Data &data1, Data &data2)
    {
        Data tmp = data1;
        data1 = data2;
        data2 = tmp;
    }
    
    void quickSort(Data *arr, long low, long high)
    {
        if(low >= high)
            return;
        long ind = 0;
        ind = partition(arr, low, high);
        if(ind != -1 && ind - 1 > low)
            quickSort(arr, low, ind - 1);
        if(ind != -1 && ind + 1 < high)
            quickSort(arr, ind + 1, high);
    
    }
    
    long partition(Data *arr, long low, long high)
    {
        if(low >= high)
            return -1;
        long len = high - low + 1;
        srand( (unsigned)time(NULL) );
        long ind = rand() % len + low;
        if(ind != high)
            SwpData(arr[ind], arr[high]);
        Data num = arr[high];
        long i = low, j = high;
        while(i < j)
        {
            while(i < j && num > arr[i])
                ++ i;
            arr[j] = arr[i];
            while(i < j && arr[j] >= num)
                -- j;
            arr[i] = arr[j];
        }
        arr[i] = num;
        return i;
    }
    
    void quickSortNew(Data *arr, long low, long high)
    {
        std::stack<Region> rstac;
        Region region;
        region.low = low;
        region.high = high;
        rstac.push(region);
        long ind = low;
        long i = 0, j = 0;
        while(!rstac.empty())
        {
            Region tmp = rstac.top();
            rstac.pop();
            i = tmp.low;
            j = tmp.high;
            ind = partition(arr, i, j);
            if(ind - 1 > i && ind != -1)
            {
                tmp.low = i;
                tmp.high = ind - 1;
                rstac.push(tmp);
            }
            if(ind + 1 < j && ind != -1)
            {
                tmp.low = ind + 1;
                tmp.high = j;
                rstac.push(tmp);
            }
        }
    }
    
    int main(int argc, char *argv[])
    {
        if(argc < 2)
        {
            printf("Usage : %s randnum.txt\n", argv[0]);
            exit(-1);
        }
        srand( (unsigned)time(NULL) );
        Data num = 0;
        Data *arr = new Data[N];  //attention 
        long i = 0;
        FILE *fp;
        fp = fopen(argv[1], "wb");
        if(NULL == fp)
        {
            printf("Open file wrong!\n");
            exit(-1);
        }
        for(i = 0; i < N; ++ i)
        {
            num = rand();
            arr[i] = num % M;
            fprintf(fp, "%ld\n", arr[i]);
        }
        fclose(fp);
    
        ///////////////////////////////////////////////
        //quickSort(arr, 0, N - 1);
    
        quickSortNew(arr, 0, N - 1);
        ///////////////////////////////////////////////
    
        char line[10240];
        snprintf(line, 10240, "%s.sort", argv[1]);
        fp = fopen(line, "wb");
        if(NULL == fp)
        {
            printf("Open file wrong!\n");
            exit(-1);
        }
        for(i = 0; i < N; ++ i)
            fprintf(fp, "%ld\n", arr[i]);
        delete [] arr; //attention
        return 0;
    }

    变量的空间分配——栈与堆

    这里值得一提的是,堆与栈空间的分配问题,定义的变量在栈空间,栈空间对数据的大小有很大的限制,最大到十万级,当直接分配百万级的空间,程序在运行时会出core,然而用堆就可以实现百万千万的空间分配。
    堆空间分配变量,new与delete,现在明白堆空间的方便与灵活之处了,也就是代码中标示 attention之处

    展开全文
  • 快速排序非递归实现及递归实现性能比较 快排是常用算法,本文不再赘述快排原理。本文主要研究快速排序非递归实现及递归实现在排序900万个int整数时的性能差异。 一 代码 package common.algorithm; import ...

    快速排序非递归实现及递归实现性能比较

    快排是常用算法,本文不再赘述快排原理。本文主要研究快速排序非递归实现及递归实现在排序900万个int整数时的性能差异。

    一 代码

    package common.algorithm;
    
    import java.util.Random;
    import java.util.Stack;
    
    /**
     * 快速排序不同版本
     * 
     * @description QuickSortNonRecursion.java
     * @author Administrator
     * @date 2018/03/23
     * @version
     */
    
    public class QuickSort {
        /**
         * quickSort TODO :快速排序递归版
         * 
         * @param arr
         * @author zhiman
         * @date 2018/03/23 下午4:30:40
         */
        public void quickSort(int[] arr) {
            int left = 0;
            int right = arr.length - 1;
            quickSort(arr, left, right);
        }
    
        /**
         * quickSort TODO :快速排序递归版
         * 
         * @param arr
         * @param left
         * @param right
         * @author zhiman
         * @date 2018/03/23 下午4:30:20
         */
        public void quickSort(int[] arr, int left, int right) {
            if (left < right) {
                int criticalPoint = partition_0(arr, left, right);
                quickSort(arr, left, criticalPoint - 1);
                quickSort(arr, criticalPoint + 1, right);
            }
        }
    
        /**
         * quickSortNonRecursion TODO :利用栈实现快速排序---非递归版
         * 
         * @param arr
         *            待排数组
         * @author zhiman
         * @date 2018/03/23 下午4:22:04
         */
        public void quickSortNonRecursion(int[] arr) {
            if (arr == null || arr.length == 0) {
                return;
            }
            int left = 0;
            int right = arr.length - 1;
            Stack<Integer> stack = new Stack<>();
            stack.push(left);
            stack.push(right);
            while (!stack.isEmpty()) {
                // 取出栈顶元素
                right = stack.pop();
                left = stack.pop();
                if (left < right) {
                    int criticalPoint = partition_0(arr, left, right);
                    stack.push(left);
                    stack.push(criticalPoint - 1);
                    stack.push(criticalPoint + 1);
                    stack.push(right);
                }
            }
        }
        /*-------------------------私有方法----------------------------*/
        /**
         * partition TODO :第一种 一次划分方法
         * 
         * @param arr
         * @param left
         * @param right
         * @return
         * @author zhiman
         * @date 2018/03/23 上午10:40:48
         */
        private int partition_0(int[] arr, int left, int right) {
            // 优化枢轴选择
            optimization(arr, left, right);
    
            int pivot = arr[left];
            while (left < right) {
                while (left < right && arr[right] >= pivot) {
                    right--;
                }
                if (left < right && arr[right] < pivot) {
                    // swap(arr,left,right);
                    arr[left] = arr[right];
                    left++;
                }
                while (left < right && arr[left] <= pivot) {
                    left++;
                }
                if (left < right && arr[left] > pivot) {
                    // swap(arr,left,right);
                    arr[right] = arr[left];
                    right--;
                }
            }
    
            arr[left] = pivot;
            return left;
        }
    
        /**
         * partition_1 TODO :更简洁的划分方法
         * 
         * @param arr
         * @param left
         * @param right
         * @return
         * @author zhiman
         * @date 2018/03/23 下午3:58:03
         */
        private int partition_1(int[] arr, int left, int right) {
            // arr[right]为枢轴
            // 指向比枢轴小的数组最后一个位置,j指向未排序的第一个数据
            optimization(arr, left, right);
            int i = left - 1;
            int j = i + 1;
            for (; j < right; j++) {
                if (arr[j] <= arr[right]) {
                    i++;
                    swap(arr, i, j);
                }
            }
            i++;
            swap(arr, i, right);
            return i;
        }
    
        /**
         * partition_2 TODO :第二种 一次划分方法
         * 
         * @param arr
         * @param left
         * @param right
         * @return
         * @author zhiman
         * @date 2018/03/23 下午5:00:27
         */
        private int partition_2(int[] arr, int left, int right) {
    
            optimization(arr, left, right);
            int pivot = arr[left];
            // 记录left位置
            int i = left;
            while ( left < right  ) {
                while(left < right && arr[left] <= pivot){
                    left++;
                }
                while(left < right && arr[right] >= pivot){
                    right--;
                }
                if ( left < right ) {
                    swap(arr, left, right);
                }
            }
            // left 要么指向最后一个小于枢轴的元素,要么指向第一个大于枢轴的元素
            int pos = arr[left] < pivot? left : left-1;
            swap(arr, i, pos);
            return pos;
        }
    
    
        /**
         * swap TODO :交换数组元素
         * 
         * @param arr
         * @param left
         * @param pos
         * @author zhiman
         * @date 2018/03/23 上午10:56:40
         */
        private void swap(int[] arr, int pos1, int pos2) {
            int temp = arr[pos1];
            arr[pos1] = arr[pos2];
            arr[pos2] = temp;
        }
    
        /**
         * optimization TODO :随机选择枢轴,避免快排出现最坏情况
         * 
         * @param arr
         * @param left
         * @param right
         * @author zhiman
         * @date 2018/03/23 下午5:05:31
         */
        private void optimization(int[] arr, int left, int right) {
            Random random = new Random();
            int pos = random.nextInt(right - left + 1) + left;
            swap(arr, left, pos);
        }
    
        /*-------------------------测试方法----------------------------*/
        public static void main(String[] args) {
            Random random = new Random();
            int[] arr = new int[9000000];
            for (int i = 0; i < 9000000; i++) {
                int pos = random.nextInt(9000000);
                arr[i] = pos;
            }
    
            int[] arr1 = new int[9000000];
            System.arraycopy(arr, 0, arr1, 0, 9000000);
    
            long start = System.currentTimeMillis();
            new QuickSort().quickSortNonRecursion(arr);
            long end = System.currentTimeMillis();
            System.out.println("非递归:" + (end - start) + "ms");
    
            start = System.currentTimeMillis();
            new QuickSort().quickSort(arr1);
            end = System.currentTimeMillis();
            System.out.println("递归:" + (end - start) + "ms");
        }
    }
    

    二 结果

    注:

    1、此处parttion_0、parttion_1、parttion_2 分别对应上面代码的parttion_0、parttion_1、parttion_2 一次划分方法
    2、做了多次试验,结果与下图类似,故只选取下图三次结果
    3、上述代码对快速排序算法做了改进,避免快排最坏情况发生

    这里写图片描述

    三 结论

    1、递归实现速度优于非递归实现。这是因为数据量较大时,非递归实现时、栈的压栈、出栈、扩容耗费了大量时间;
    2、无需担心JVM栈溢出的情况,在堆内存为150m时:900万数据(900万 X 2 Byte大约8.5G数据)递归实现没出现OoM现象
    这里写图片描述

    四 快排优化方法

    1 当当待排数据规模小到一定程度时,快排的性能会降低,此时可以改快排算法为插入排序算法。一般当将10作为两种算法切换的临界点
    2 当待排数据规模小到一定程度时,快排的性能会降低,此时可以改快排算法为插入排序算法。一般当将10作为两种算法切换的临界点
    3 每次划分将数据分为三堆,大于枢轴元素的,小于枢轴元素的,和等于枢轴元素的,传送门:传送门 ,这种元素避免了重复元素问题

    展开全文
  • 快速排序partition过程常见的两种写法+快速排序非递归实现
    展开全文
  • 这里借鉴了二叉树后序遍历的非递归思想,

    这里借鉴了二叉树先序遍历的非递归算法。


    <span style="font-size:14px;">typedef struct Ele {
    	Ele(int start_ = 0, int end_ = 0) : start(start_), end(end_) {}
    	int start;
    	int end;
    } Ele; 
    
    int quickSort(int *list, int start, int end) {
    	if(start >= end) {
    		return - 1;
    	} 
    	int temp = list[start];
    	int i = start;
    	int j = end;
    	while(i < j) {
    		while(i < j && list[j] >= temp) {
    			j --;
    		}
    		if(i < j) {
    			list[i] = list[j];
    			i ++;
    		}
    		while(i < j && list[i] <= temp) {
    			i ++;
    		}
    		if(i < j) {
    			list[j] = list[i];
    			j --;
    		}
    	}
    	list[i] = temp;
    	return i;
    }
    
    void sort(int *list, int len) {
    	stack<Ele> sta;
    	sta.push(Ele(0, len - 1));
    	int mid;
    	Ele ele;
    	while(sta.size() > 0) {
    		ele = sta.top();
    		sta.pop();
    		if((mid = quickSort(list, ele.start, ele.end)) >= 0) {
    			sta.push(Ele(mid + 1, ele.end));
    			sta.push(Ele(ele.start, mid - 1));
    		}
    	}
    }
    
    int main(void) {
    	int str[10] = {9, 8, 7, 6, 5, 4, 3, 2, 1, 0};
    	sort(str, 10);
    	for(int i = 0; i < 10; i ++) {
    		cout << str[i] << " ";
    	}
    	cout << endl;
    	return 0;
    }</span>



    展开全文
  • 快速排序非递归实现--python

    千次阅读 2018-06-01 14:11:37
    主要思想是:每次把待排序数组分为两部分,左边小于轴右边大于轴,把分开的数组的收尾数组的索引存到辅助栈空间里,替换递归。两种思路: 思路一:严老师数据结构里面的思路 def partition(nums,low,high): high_...
  • 一、快速排序递归实现 快速排序的思想是每次找到一个元素的位置,再在以这个元素分隔的两个子范围中分别再各自确定一个元素的位置,子子范围也是如此操作,当某个子范围只有一个元素或者没有元素时,便不再做任何...
  • 快速排序(三种算法实现和非递归实现)

    万次阅读 多人点赞 2017-11-29 18:41:44
    快速排序(Quick Sort)是对冒泡排序的一种改进,基本思想是选取一个记录作为枢轴,经过一趟排序,将整段序列分为两个部分,其中一部分的值都小于枢轴,另一部分都大于枢轴。然后继续对这两部分继续进行排序,从而使...
  • 快速排序 非递归实现 递归实现 C++代码 java实现
  • 快速排序的递归和非递归实现

    千次阅读 2016-02-28 16:28:12
    写在前面对于经典的排序算法大家...当然,对于分治类型的算法,一般都存在递归解法和非递归解法两种,这里也给出两种实现。代码实现package com.nggirl.test.sort;import java.util.HashSet; import java.util.Set;publ
  • 快速排序的递归与非递归实现

    千次阅读 2020-01-20 12:38:21
    快速排序 取一个标杆元素pivot ...递归实现易于理解,其主要思想就是通过递归来不断对左右两个子区间进行快速排序直到排序完成。 public int[] quickSort(int[]arr){ quickSort(arr,0, arr.len...
  • 快速排序 非递归实现方式的完整源代码和测试结果。
  • 快速排序非递归用队列实现c++

    千次阅读 2018-12-26 16:40:03
    快速排序非递归用队列实现 第一次写博客,写的不是太好,但不是我邢标吹牛耐心看保证你会!!!! ① 先了解快排原理: 假设有一个数组 6 2 1 7 9 3 4 5 8 10 1.先找一个数作为参考对象,为了方便,就以数组的第...
  • 两种方法: 传统的递归快速排序 采用非递归堆栈模拟
  • 快速排序 非递归

    2016-04-21 15:18:01
    快速排序非递归实现, 借助栈。
  • 利用栈来消除递归 模拟快速排序的过程 实现非递归快速排序
  • 快速排序的递归和非递归实现方法 参考来源:点击打开链接 /* 快速排序的两种实现方法: 1、递归实现 2、非递归实现 */ #include #include using namespace std; //以a[0]作为枢轴,将数组分开 int partition...
  • 快速排序非递归实现使用栈和队列实现均可。 只是处理左右段先后顺序的不同!注意:这里没有给出模版类的实现。需要模版类稍作改动即可。快速排序递归实现void swap(int &a,int &b){ int c =a; a = b; b = c; }...
  • /*快排 - 递归实现nlogn*//*原理: 快速排序(Quicksort)是对冒泡排序的一种改进。 快速排序由C. A. R. Hoare在1962年提出。它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据...
  • 快速排序非递归实现

    千次阅读 2013-09-25 10:12:27
    今天研究了一下快速排序如何用非递归算法解决。下面代码,自认为非常简洁,通过简单测试没有发现任何问题,供大家参考。 本程序利用了“栈” 代码如下: #include #include #include #include using namespace ...
  • 快速排序非递归实现-----c语言

    千次阅读 多人点赞 2018-09-25 17:53:36
      前面我们讲解了快速排序的递归实现,但若是待排序的数量非常大且杂乱无章,每层循环都使用递归调用,会很容易造成栈溢出,所以我们可以将快速排序设计为非递归实现。 递归实现快速排序算法详解   快速排序是从...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 49,254
精华内容 19,701
关键字:

快速排序非递归实现