关于快速排序

常用

1.sort()方法:

var a = [5,29,23,37,27,44];
function sortNum(a,b){
        return a-b;
    }
alert(a.sort(sortNum));
  • 若 a 小于 b,在排序后的数组中 a 应该出现在 b 之前,则返回一个小于 0 的值。
  • 若 a 等于 b,则返回 0。
  • 若 a 大于 b,则返回一个大于 0 的值。

2.

var a = [5,29,23,37,27,44];
    function quickSort(arr){
        if(arr.length <=1){
            return arr;
        }
        var num = Math.floor(arr.length/2);
        var numValue = arr.splice(num,1);
        var left = [];
        var right = [];
        for(var i =0,len=arr.length;i<len;i++){
            if(arr[i]<numValue){
                left.push(arr[i]);
            }
            if(arr[i]>numValue){
                right.push(arr[i]);
            }

        }
        return quickSort(left).concat(numValue,quickSort(right));

    }
    alert(quickSort(a));

这种方法是选用一个中间数,每个数轮流与这个中间数进行比较,比这个中间数小那就放进数组left里面,反之则放入数组right

利用递归的方式重复进行比较,用concat将这些数组拼合起来

时间: 09-06

关于快速排序的相关文章

快速排序

快速排序的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列. 快速排序是一种不稳定的排序算法,也就是说,多个相同的值的相对位置也许会在算法结束时产生变动 快速排序是C.R.A.Hoare于1962年提出的一种划分交换排序.它采用了一种分治的策略,通常称其为分治法(Divide-and-ConquerMethod). 该方法的基本思想是:

快速排序——Python

快速排序: 在一组数据中选择一个基准值,让后将数据分为两个部分,一部分大于基准,一部分小于基准,然后按此方法将两个部分分组,直到不能再分为止. 需要明白一个概念递归和分而治之的概念. Python实现: 1 # 快速排序 2 3 import random 4 5 def quick_sort(arr): 6 # 边界条件 7 if len(arr) < 2: 8 return arr 9 key = random.choice(arr) # 选择基准 10 left = [i for i in

快速排序的实现(不保证效率

众所周知,快速排序的核心是分治的思想,选一个基准出来,然后通过划分操作,使得,该元素最终处于的位置的左边的元素都小于等于它,右边的元素都大于等于它 划分操作就是两次递归嘛,没什么的,关键在于不借助外部空间我们如何实现划分操作 首先我们不知道该元素放在哪里,显然这是最后才能确定的, 我了解到一种填坑法的实现... 那就是首先保存第一个位置的值,然后从后向前扫描第一个小于x的值,我们就可以直接覆盖第一个位置的值,然后我们再从前向后找大于x的值, 把后面的坑填上 下面枚举几种情况 基准前后有相同数量的

快速排序的总结

快速排序的思想是分而治之,利用递归达到快速排序的效果 首先要选定一个基准数,一般选择最左边的数为基准数,排序的目标就是让这个基准数的左边全小于这个基准数,右边全大于这个基准数.然后以这个基准数为分隔线,在左右两侧再次调用这个排序的函数,直到全部有序.简述过程: 以  8 9 4 7 2 6 首选 1. 选择两个哨兵 i,j 分别指向8,6,基准数为8 2.从j哨兵开始,因为j指向的6小于基准数8,不符合j指向的数都要大于8的要求,所以将j指向的数覆盖i指向的数,同时i指向的数变成9 6 9 4

[数据结构] 快速排序

基本思想 快速排序(Quicksort)是对冒泡排序的一种改进,又称划分交换排序(partition-exchange sort. 快速排序使用分治法(Divide and conquer)策略来把一个序列(list)分为两个子序列(sub-lists). 步骤为: ①.从数列中挑出一个元素,称为"基准"(pivot) ②.重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边).在这个分区结束之后,该基准就处于数列的中间位置.这个称

使用JAVA直观感受快速排序与冒泡排序的性能差异

初学算法,肯定会编写排序算法 其中两个最为有名的就是冒泡排序和快速排序 理论上冒泡排序的时间复杂度为O(N^2),快速排序的时间复杂度为O(NlogN) 下面本门使用JAVA,分别编写三段排序程序 对十万个0-9999的整数进行一次冒泡排序 对十万个0-9999的整数进行1000次快速排序,使用递归完成 对十万个0-9999的整数进行1000次快速排序,使用堆栈完成 对十万个0-9999的整数进行一次冒泡排序: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

Swift实现的快速排序及sorted方法的对比

Swift语言有着优秀的函数式编程能力,面试的时候面试官都喜欢问我们快速排序,那么用Swift如何实现一个快速排序呢?首先扩展Array类: extension Array { var decompose : (head: T, tail: [T])? { return (count > 0) ? (self[0], Array(self[1..<count])) : nil } } 属性decompose的作用是返回数组中的第一个元素和剩下的元素,注意这个属性是可选型的,当count为0的时

Java实现排序算法之快速排序

一.综述 快速排序是交换排序中的一种,平均算法复杂度是O(nlogn),最坏O(n*n).下面用Java实现一个快速排序,并用注释的方式解释了思想和原理. 二.Java实现堆排序 三.结果检验 版权声明:本文为博主原创文章,未经博主允许不得转载.

单链表排序——快速排序实现

利用快速排序,同向一前一后两个指针 #ifndef LIST_H_ #define LIST_H_ #include <iostream> #include <utility> class List { private: struct ListNode { int _value; ListNode* _next; }; public: List(): _head(nullptr) {} ~List() { while (nullptr != _head) { auto tmp =

排序之快速排序

package com.xsz.demo; /**     * @author cwqi    * @date 2015-1-6    */ //排序之快速排序,基本思路為分治+挖坑,方法有兩種:一是雙邊掃面:二是單邊掃描. public class QuickSort { public static void main (String[] args){ int a[] ={2,3,30,1,4,56,2,7,3,8}; //int a[] ={4,5,6,2,7,3,8}; //int a[]