快速排序的两种写法

柔光的暖阳◎ 2023-03-12 09:17 15阅读 0赞

1.左端点作为关键字。

#include<iostream>
    using namespace std;
    int a[100000],n;
    void print()
    { 
    	for(int i=1;i<=n;i++)
    	cout<<a[i]<<' ';
    	cout<<endl;
    }
    void qsort(int start,int end)
    { 
    	if(start>=end)
    	return ;
    	int key=a[start];
    	int i=start,j=end;
    	while(i<j)
    	{ 
    		while(a[j]>=key&&i<j)
    		j--;
    		swap(a[i],a[j]);
    		while(a[i]<=key&&i<j)
    		i++;
    		swap(a[i],a[j]);
    	}
    	//cout<<"key="<<key<<" a[i]="<<a[i];
    	print();
    	qsort(start,i-1);
    	qsort(i+1,end);
    }
    int main()
    { 
    	ios::sync_with_stdio(false);
    	int i;
    	cin>>n;
    	for(i=1;i<=n;i++)
    	cin>>a[i];
    	qsort(1,n);
    	return 0;
    }

2.中间点作为关键字

#include<iostream>
    using namespace std;
    int n,a[1000001];
    void qsort(int l,int r)//应用二分思想
    { 
        int mid=a[(l+r)/2];//中间数
        int i=l,j=r;
        do{ 
            while(a[i]<mid) i++;//查找左半部分比中间数大的数
            while(a[j]>mid) j--;//查找右半部分比中间数小的数
            if(i<=j)//如果有一组不满足排序条件（左小右大）的数
            { 
                swap(a[i],a[j]);//交换
                i++;
                j--;
            }
        }while(i<=j);//这里注意要有=
        if(l<j) qsort(l,j);//递归搜索左半部分
        if(i<r) qsort(i,r);//递归搜索右半部分
    }
    int main()
    { 
        cin>>n;
        for(int i=1;i<=n;i++) cin>>a[i];
        qsort(1,n);
        for(int i=1;i<=n;i++) cout<<a[i]<<" ";
    }

第二种在元素排列趋于有序的时候效率要比第一种高，第一种此时的时间效率大概为O(n).

发表评论取消回复

表情：

评论列表（有 0 条评论，15人围观）

还没有评论，来说两句吧...

相关阅读

相关快速排序图解（两种思想）

七大排序之快速排序文章目录七大排序之快速排序前言一、《算法导论》中的分区思想 1.1 算法思想 1.2 代码实现

Bertha 。/ 2023年09月25日 12:22/ 0 赞/ 60 阅读

相关快速排序的两种写法

1.左端点作为关键字。 include<iostream> using namespace std; int a[100000],n; voi

柔光的暖阳◎/ 2023年03月12日 09:17/ 0 赞/ 16 阅读

相关 php冒泡排序的两种写法

第一种： function bubbleSort($arr) { foreach ($arr as $i => &$a) {

谁践踏了优雅/ 2022年10月23日 08:13/ 0 赞/ 218 阅读

相关 vue的两种写法

<!DOCTYPE html> <html> <head> <meta charset="utf-8" /> <ti

旧城等待，/ 2022年09月10日 12:11/ 0 赞/ 271 阅读

相关快速排序的另种高效率的写法

快速排序是大家所熟知的排序算法，昨天立文问起我这个算法来；虽然代码不费力可以正常跑，可我发现里面有诸多问题；他写的代码就不公布了；首先，里面的两个小循环的位置不能随意调换的

￡神魔★判官ぃ/ 2022年08月27日 06:51/ 0 赞/ 162 阅读

相关冒泡排序BubbleSort(两种写法)

冒泡排序的核心理念是什么?那就是相邻两数比较,前面的数比后面的数小的话,就交换位置,每次循环找到该次排序的最小值,然后放到该次循环数组的队尾,因此便利到最后,留的就是最大的数.

川长思鸟来/ 2022年05月23日 09:47/ 0 赞/ 234 阅读

相关快速排序的两种实现（java）

用递归方式去做，这个比较明确，下面针对具体的方法分两种情况（1）第一种　　做两个游标，找！从前面找到比标准值大的数，从后面找到比标准值小的数，然后交换位置。以此重复

ゞ浴缸里的玫瑰/ 2022年05月16日 03:35/ 0 赞/ 155 阅读

相关两种Ajax写法

Ajax:(Asynchronous Javascript And XML)简称为异步的js和xml js中有两种写法： //原生js写法 functio

﹏ヽ暗。殇╰゛Y/ 2022年03月28日 15:11/ 0 赞/ 319 阅读

相关 ajax的两种写法

一、原生ajax的实现 1.什么是ajax？ ajax是异步的javas和xml（ Asynchronous JavaScript And XML）。通过在后台与服务器

古城微笑少年丶/ 2022年03月27日 05:37/ 0 赞/ 375 阅读

相关 animate两种写法

animate.css <image class="logo animate__animated " :class="{ animate_

绝地灬酷狼/ 2021年07月25日 17:33/ 0 赞/ 555 阅读