文档章节

快速排序

熊友良
 熊友良
发布于 2014/10/21 22:46
字数 398
阅读 173
收藏 11

这几天在找工作,今天被问到快速排序,结果想不出来快速排序怎么弄的;回来搜索了一下,现在记录下来,方便以后查看。

注意:快速排序不会直接得到最终结果,只会把比k大和比k小的数分到k的两边。(你可以想象一下i和j是两个机器人,数据就是大小不一的石头,先取走i前面的石头留出回旋的空间,然后他们轮流分别挑选比k大和比k小的石头扔给对面,最后在他们中间把取走的那块石头放回去,于是比这块石头大的全扔给了j那一边,小的全扔给了i那一边。只是这次运气好,扔完一次刚好排整齐。)为了得到最后结果,需要再次对下标2两边的数组分别执行此步骤,然后再分解数组,直到数组不能再分解为止(只有一个数据),才能得到正确结果。 ------ 取自百度百科(链接

C/C++ 实现:

<!-- lang: cpp -->
void quick_sort(int* a, int low, int high){
if (low >= high) {
    return;
}
int first = low;
int last = high;
int key = a[first];
while (first < last) {
    while (first < last && a[last] >= key) {
        --last;
    }
    a[first] = a[last];
    
    while (first < last && a[first] <= key) {
        ++first;
    }
    a[last] = a[first];
}
a[first] = key;
quick_sort(a, low, first-1);
quick_sort(a, first+1, high);
}

© 著作权归作者所有

熊友良
粉丝 4
博文 18
码字总数 6327
作品 0
广州
程序员
私信 提问
常用的简单排序算法集合(更新中)

/** 冒泡排序 /public static void Bubble_Sort(int[] a) {for (int i = 0; i < a.length - 1; i++) {for (int j = 0; j < a.length - i - 1; j++) {if (a[j] > a[j + 1]) {a[i] = a[i] + a[......

维特的烦恼
2014/04/26
140
1
每天学习一点儿算法--快速排序

快速排序是一种常用的优雅的排序算法,它使用分而治之的策略。 那么分而治之(D&C)是一种怎样的策略呢? 分而治之 分而治之(D&C)的要点只有两个: 找出简单的基线问题 确定如何缩小问题的...

爱吃西瓜的番茄酱
2018/01/11
0
0
快速排序详解 Java实现

一、快速排序的优缺点 对一个东西,首先要讲他的利与弊,才知道怎么使用它。快速排序适用于各种不同的输入数据且在一般应用中比其他排序都要快得多。快速排序引人注目的特点包括它是原地排序...

小车车
2016/09/03
71
0
好程序员Java教程教你5分钟了解快速排序

好程序员Java教程教你5分钟了解快速排序,前言: 快速排序是面试中经常会问到的一种排序算法,对比其他一些排序算法,快速排序的平均时间相对较少。 快速排序思想介绍 快速排序使用了分治的思...

好程序员IT
06/21
38
0
快速排序算法QuickSort

1.说明 快速排序法(quicksort)是目前所公认最快的排序方法之一(视解题的对象而定),虽然快速排序法在最差状况下可以达O(n2),但是在多数的情况下,快速排序法的效率表现是相当不错的。快...

嗯哼9925
2017/12/14
0
0

没有更多内容

加载失败,请刷新页面

加载更多

ReentrantLock的可重入特性

在自旋分布式锁实现 中我们已经分析了ReentrantLock的自旋特性,现在我们来分析一下它的可重入特性。 可重入特性其实说白了就是当获得锁的线程解锁后,重新来获取锁的时候会判断自己以前是否...

算法之名
43分钟前
6
0
js如何控制table中的某一行动态置顶

两行代码搞定: $('#'+item.roadCode).fadeOut().fadeIn();//获取到需要置顶的行 $(".table").prepend($('#'+item.roadCode)); 其中,fadeOut()方法 作用 --- 从可见到隐藏 如下: prepend(......

码妞
今天
4
0
四种解决Nginx出现403 forbidden 报错的方法

我是在在本地用虚拟机中通过yum安装nginx的,安装一切正常,但是访问时报403, 于是查看nginx日志,路径为/var/log/nginx/error.log。打开日志发现报错Permission denied,详细报错如下: 1....

dragon_tech
今天
3
0
获取RestResultResponse返回的值

Springboot项目,需要调其他服务的接口,返回值类型是RestResultResponse 打断点的结果集是这个 打印出来的getData(): [{id=3336b624-8474-4dd9-bd5b-c7358687c877, paraNo=104, para=Postpo...

栾小糖
今天
4
0
【小学】 生成10以内的加减法

#!/usr/bin/env python# coding: utf-8from random import randrange# 题目的最大数值R_MAX = 10# 生成的题目的数量R_PAGE = 70# 生成减法列表def get_sub_list():...

Tensor丨思悟
今天
11
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部