快速排序【模板】

简介:

一、递归版本

手打递归版本

void quickSort(int *arr, int left,int right) {

    if(left>=right)
        return;

    int i=left,j=right;
    int standard = arr[left];

    while(i<j) {

        //find some elements bigger than standard
        while( i<j && arr[i] < standard)
            ++i;

        //find some elements smaller than standard
        while( i<j && arr[j] > standard)
            --j;

        //exchange arr.i and arr.j
        swap(arr[i],arr[j]);
    }
    // i == j where the standard should be

    quickSort(a,left,i-1);
    quickSort(a,i+1,right);
}

《数据结构理论与实践》版本:

int Partition(int *arr, int i,int j) {

    arr[0] = arr[i]; //arr[0] is a temp space

    while(i<j) {

        while(i<j && arr[j] >= arr[0]) --j;

        if( i < j) { //move the smaller element to the front
            arr[i] = arr[j];
            ++i;
        }

        while(i<j && arr[i] < arr[0]) ++i;

        if( i < j) { //move the bigger element to the tail
            arr[j] = arr[i];
            --j;
        }
    }

    arr[i] = arr[0];
    return i;
}

void quickSort(int *arr, int left,int right) {

    int i;
    if(left<right) {
        i = Partition(arr,left,right); //divide the arr into 2 parts
        quickSort(arr,left,i-1);
        quickSort(arr,i+1,right);
    }
}

上面的版本都会有TLE
递归改进版(poj 2623 AC):

void quickSort(int *arr, int left, int right){
    int i = left, j = right;
    int mid = arr[(i+j)/2];
    while(i <= j){
        while(arr[i] < mid) i ++;
        while(arr[j] > mid) j --;
        if(i <= j){
            int tmp;
            tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp;
            i ++; j --;
        }
    }
    if(i < right) quickSort(arr,i, right);
    if(left < j) quickSort(arr,left, j);
}

二、非递归版本

/**使用栈的非递归快速排序**/
template<typename Comparable>
void quicksort2(vector<Comparable>
 &vec,int low,int high){
    stack<int>
 st;
    if(low<high){
        int mid=partition(vec,low,high);
        if(low<mid-1){
            st.push(low);
            st.push(mid-1);
        }
        if(mid+1<high){
            st.push(mid+1);
            st.push(high);
        }
        //其实就是用栈保存每一个待排序子串的首尾元素下标,下一次while循环时取出这个范围,对这段子序列进行partition操作
        while(!st.empty()){
            int q=st.top();
            st.pop();
            int p=st.top();
            st.pop();
            mid=partition(vec,p,q);
            if(p<mid-1){
                st.push(p);
                st.push(mid-1);
            }
            if(mid+1<q){
                st.push(mid+1);
                st.push(q);
            }      
        }
    }
}
相关文章
|
JavaScript NoSQL Java
高并发架构系列:Redis为什么是单线程、及高并发快的3大原因详解
Redis的高并发和快速原因 1.redis是基于内存的,内存的读写速度非常快;2.redis是单线程的,省去了很多上下文切换线程的时间;3.redis使用多路复用技术,可以处理并发的连接。非阻塞IO 内部实现采用epoll,采用了epoll+自己实现的简单的事件框架。
4362 0
|
存储 算法 NoSQL
TinyKv介绍
TinyKv介绍
522 1
|
存储 算法
【堆】数据结构堆的实现(万字详解)
【堆】数据结构堆的实现(万字详解)
626 0
|
关系型数据库 MySQL 数据库
什么是内连接、外连接、交叉连接、笛卡尔积呢?
什么是内连接、外连接、交叉连接、笛卡尔积呢?
|
7月前
|
图形学
Unity 射线移动物体Ray
在Unity中,通过射线检测实现3D物体的拖拽和移动。射线由起点和方向组成,使用`Physics.Raycast`检测与物体的交点。点击物体时,记录位置偏移量,拖动过程中更新物体位置。代码包括基本拖拽和上下拖动功能,适用于正交摄像机场景。测试时为物体设置特定标签(如&quot;JQR&quot;)以便区分和操作。 示例代码展示了如何通过鼠标事件控制物体移动,并结合层级掩码优化射线检测。具体实现包括:点击选中物体、拖动更新位置、释放鼠标取消选择。此外,提供了上下拖动的额外功能,通过按键切换模式。
|
11月前
|
存储 算法 C++
【搜索算法】 跳马问题(C/C++)
【搜索算法】 跳马问题(C/C++)
|
Python
`else`子句可以与`while`循环结合
【9月更文挑战第07天】
309 8
|
11月前
|
网络协议 索引
Flutter获取手机的IP地址
Flutter获取手机的IP地址