C/C++实现快速排序的方法

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

C/C++ 实现：

代码如下:

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);
}

赞 (0)

相关推荐

  • c++快速排序详解

    c++快速排序详解

    说一说快速排序 快速排序,实际中最常用的一种排序算法,速度快,效率高,在N*logN的同等级算法中效率名列前茅.· 基本思想:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分所有数据要小,然后再按此方法对这两部分数据分别进行快速排序.整个排序过程可以递归进行,以此达到整个数据变成有序序列. 将数列变成上述形式,这一步很关键,做好这一步,才能对主元左右的部分进行递归调用.以下是实现这一部分的代码: int partition_sort(int arr[],int l

  • C++快速排序的分析与优化详解

    相信学过数据结构与算法的朋友对于快速排序应该并不陌生,本文就以实例讲述了C++快速排序的分析与优化,对于C++算法的设计有很好的借鉴价值.具体分析如下: 一.快速排序的介绍 快速排序是一种排序算法,对包含n个数的输入数组,最坏的情况运行时间为Θ(n2)[Θ 读作theta].虽然这个最坏情况的运行时间比较差,但快速排序通常是用于排序的最佳的实用选择.这是因为其平均情况下的性能相当好:期望的运行时间为 Θ(nlgn),且Θ(nlgn)记号中隐含的常数因子很小.另外,它还能够进行就地排序,在虚拟内存

  • c++实现对输入数组进行快速排序的示例(推荐)

    废话不多说,直接上代码 #include "stdafx.h" #include <iostream> #include <string> #include <vector> using namespace std; void quickSort(vector<int> &a, int, int); void swap(int &a, int&b); vector<string> split(strin

  • C++ 先对数组排序,在进行折半查找

    第一步:输入15个整数 第二步:对这15个数进行排序 第三部:输入一个数,在后在排好序的数中进行折半查找,判断该数的位置 实现代码如下: 方法一: 选择排序法+循环折半查找法 复制代码 代码如下: #include<iostream>using namespace std;int main(){ int a[15]; int n,i; void array_sort(int a[], int n); int zeban(int a[], int start ,int end,int n); c

  • java实现快速排序的方法

    本文实例讲述了java实现快速排序的方法.分享给大家供大家参考.具体实现方法如下: public class Quick { public static int[] Data = { 9, 8, 7, 4, 1, 12, 15, 63, 15, 20 }; public static void quick(int left, int right) { int i, j; int Pivot; int temp; i = left; j = right; Pivot = Data[(left+ri

  • php关联数组快速排序的方法

    本文实例讲述了php关联数组快速排序的方法.分享给大家供大家参考.具体如下: <?php function qsort($a,$f) { qsort_do(&$a,0,Count($a)-1,$f); } function qsort_do($a,$l,$r,$f) { if ($l < $r) { qsort_partition(&$a,$l,$r,&$lp,&$rp,$f); qsort_do(&$a,$l,$lp,$f); qsort_do(&am

  • JavaScript实现快速排序的方法

    本文实例讲述了JavaScript实现快速排序的方法.分享给大家供大家参考.具体实现方法如下: <html> <head> <script> function quickSort(input) { if (input.length <= 1) return input; var pivot = Math.floor(Math.random()*input.length) var less = [], greater=[]; var pivotElem = inpu

  • php简单实现快速排序的方法

    本文实例讲述了php简单实现快速排序的方法.分享给大家供大家参考.具体实现方法如下: function quicksort($seq) { if(!count($seq)) return $seq; $k = $seq[0]; $x = $y = array(); for($i=count($seq); --$i;) { if($seq[$i] <= $k) { $x[] = $seq[$i]; } else { $y[] = $seq[$i]; } } return array_merge(q

  • JS排序算法之希尔排序与快速排序实现方法

    本文实例讲述了JS排序算法之希尔排序与快速排序实现方法.分享给大家供大家参考,具体如下: 希尔排序: 定义一个间隔序列,例如是5,3,1.第一次处理,会处理所有间隔为5的,下一次会处理间隔为3的,最后一次处理间隔为1的元素.也就是相邻元素执行标准插入排序. 在开始最后一次处理时,大部分元素都将在正确的位置,算法就不必对很多元素进行交换,这是比插入元素高级的地方. 时间复杂度O(n*logn) function shellSort(){ var N=arr.length; var h=1; whi

  • PHP递归实现快速排序的方法示例

    本文实例讲述了PHP递归实现快速排序的方法.分享给大家供大家参考,具体如下: 首先我们要理解一下快速排序的原理:找到当前数组中的任意一个元素(一般选择第一个元素),作为标准,新建两个空数组,遍历整个数组元素,如果遍历到的元素比当前的元素要小,那么就放到左边的数组,否则放到右面的数组,然后再对新数组进行同样的操作. 不难发现,这里符合递归的原理,所以我们可以用递归来实现. 使用递归,则需要找到递归点和递归出口: 递归点:如果数组的元素大于1,就需要再进行分解,所以我们的递归点就是新构造的数组元素个

  • Python一行代码实现快速排序的方法

    今天将单独为大家介绍一下快速排序! 一.算法介绍 排序算法(Sorting algorithm)是计算机科学最古老.最基本的课题之一.要想成为合格的程序员,就必须理解和掌握各种排序算法.其中"快速排序"(Quicksort)使用得最广泛,速度也较快.它是图灵奖得主C. A. R. Hoare(托尼·霍尔)于1960时提出来的. 二.算法原理 快排的实现方式多种多样,猪哥给大家写一种容易理解的:分治+迭代,只需要三步: 在数列之中,选择一个元素作为"基准"(pivot

  • JavaScript实现快速排序的方法分析

    本文实例讲述了JavaScript实现快速排序的方法.分享给大家供大家参考,具体如下: 思想: 通过分治思想.递归方法将数据依次分解为包含较小元素和较大元素的不同子序列 1.在数组中选择一个元素为基准 2.对数组进行遍历,小于基准的元素都移到基准的左边,大于基准的元素都移到基准的右边 3.对基准左边和右边的两个子集,不断重复前两步,直到所有子集只剩下一个元素为止 实现代码: function sqort(arr){ if(arr.length===0){ return []; } var lef

  • Python实现快速排序的方法详解

    本文实例讲述了Python实现快速排序的方法.分享给大家供大家参考,具体如下: 说起快排的Python实现,首先谈一下,快速排序的思路: 1.取一个参考值放到列表中间,初次排序后,让左侧的值都比他小,右侧的值,都比他大. 2.分别对左侧和右侧的部分递归第1步的操作 实现思路: 两个指针left,right分别指向列表的第一个元素和最后一个元素,然后取一个参考值,默认为第一个列表的第一个元素list[0],称为K 然后left指向的值先和参考值K进行比较,若list[left]小于或等于K值,le

  • C/C++实现快速排序的方法

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

随机推荐