`
lvwenwen
  • 浏览: 926420 次
  • 性别: Icon_minigender_1
  • 来自: 魔都
社区版块
存档分类
最新评论

快速排序算法原理与实现/交换排序

阅读更多
快速排序的大致思想为取到中间位置的元素,其他元素和其一一比较,分列左右,然后左右再迭代使用以上步骤

Java代码 
quickSort:function(arr) { 
    if (arr.length <= 1) {return arr;} 
    var pivotIndex = Math.floor(arr.length / 2); 
    var pivot = arr.splice(pivotIndex, 1); 
    var left = []; 
    var right = []; 
    for (var i = 0; i < arr.length; i++){ 
        if (arr[i] < pivot){ 
            left.push(arr[i]); 
            }else{ 
            right.push(arr[i]); 
            } 
        } 
    return quickSort(left).concat(pivot, quickSort(right)); 
}, 
quickSortObjArr:function(objArr,key) { 
    if (objArr.length <= 1) {return objArr;} 
    var pivotIndex = Math.floor(objArr.length / 2); 
    //var pivot = objArr.splice(pivotIndex, 1); 
    var pivot = objArr[pivotIndex]; 
    objArr.splice(pivotIndex, 1);    
    var left = []; 
    var right = []; 
    for (var i = 0; i < objArr.length; i++){      
        if (objArr[i][key] < pivot[key]){             
            left.push(objArr[i]); 
            }else{ 
            right.push(objArr[i]); 
            } 
        } 
    return quickSortObjArr(left,key).concat(pivot, quickSortObjArr(right,key)); 


快速排序的基本思想是
通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。
快速排序的一般性策略
设要排序的数组是A[0]……A[N],首先任意选取一个数据(通常选用第一个数据)作为关键数据,然后将所有比它小的数都放到它前面,所有比它大的数都放到它后面,这个过程称为一趟排序。
具体步骤
以第一个数据作为基准数据,并赋值给temp变量。
定义两个变量i,j使其初始值i=1,j=N。
无限遍历直到找到基准数的位置为止,寻找基准数位置方法如下,
由j开始向前搜索即(j = j-1),直到找到第一个A[j] < temp时停止向前搜索。
由i开始向后搜索即(i = i+1),直到找到第一个A[i] > temp时停止向后搜索。
当 i < j 时 交换A[i] 和 A[j] 的位置,否则退出遍历。即j就是基准数的最终位置。
将基准数与A[j]的位置互换,第一趟排序完成。
将比基准数小的值列与比基准数大的值列继续递归排序从而最终排序。
Java代码 
/**
* 快速排序
* @param arr 待排数组
* @param low 待排数组低位下标
* @param higth 待排数组高位下标
*/ 
public void quickSort(int[] arr,int low,int higth){ 
    //{3,2,1,20,6,5,16,8}  
    if(low < higth){ 
        int temp = arr[low]; 
        int i = low + 1; 
        int j = higth; 
        for(;;){ 
            while((i <=higth)&&arr[i] < temp){ 
                i++; 
            }  
            while((j >=low)&&arr[j] > temp){ 
                j--; 
            } 
            if(i < j){ 
                swap(arr, i, j); 
            }else{ 
                break; 
            } 
             
        } 
        swap(arr, low, j); 
        quickSort(arr, low, j-1); 
        quickSort(arr, j+1, higth); 
    } 
 
    // 

 
public void swap(int[] arr, int i,int j){ 
    int temp = arr[j]; 
    arr[j] = arr[i]; 
    arr[i] = temp; 


思想

快速排序算法  例 确定1个数值 大的在后面 小的那前面 在以数值为中心分割 前后2个数组分别做快速排序~如此递归!

下面是1个demo

设要排序的数组是A[0]……A[N-1],首先任意选取一个数据(通常选用第一个数据)作为关键数据,然后将所有比它小的数都放到它前面,所有比它大的数都放到它后面,这个过程称为一趟快速排序。值得注意的是,快速排序不是一种稳定的排序算法,也就是说,多个相同的值的相对位置也许会在算法结束时产生变动。
  一趟快速排序的算法是:
  1)设置两个变量I、J,排序开始的时候:I=0,J=N-1;
  2)以第一个数组元素作为关键数据,赋值给key,即 key=A[0];
  3)从J开始向前搜索,即由后开始向前搜索(J=J-1),找到第一个小于key的值A[J],并与key交换;
  4)从I开始向后搜索,即由前开始向后搜索(I=I+1),找到第一个大于key的A[I],与key交换;
  5)重复第3、4、5步,直到 I=J; (3,4步是在程序中没找到时候j=j-1,i=i+1,直至找到为止。找到并交换的时候i, j指针位置不变。另外当i=j这过程一定正好是i+或j-完成的最后另循环结束。)
  例如:待排序的数组A的值分别是:(初始关键数据:X=49) 注意关键X永远不变,永远是和X进行比较,无论在什么位子,最后的目的就是把X放在中间,小的放前面大的放后面。
  A[0] A[1] A[2] A[3] A[4] A[5] A[6]:
  49 38 65 97 76 13 27
  进行第一次交换后:27 38 65 97 76 13 49
  ( 按照算法的第三步从后面开始找)
  进行第二次交换后:27 38 49 97 76 13 65
  ( 按照算法的第四步从前面开始找>X的值,65>49,两者交换,此时:I=3 )
  进行第三次交换后:27 38 13 97 76 49 65
  ( 按照算法的第五步将又一次执行算法的第三步从后开始找
  进行第四次交换后:27 38 13 49 76 97 65
  ( 按照算法的第四步从前面开始找大于X的值,97>49,两者交换,此时:I=4,J=6 )
  此时再执行第三步的时候就发现I=J,从而结束一趟快速排序,那么经过一趟快速排序之后的结果是:27 38 13 49 76 97 65,即所有大于49的数全部在49的后面,所有小于49的数全部在49的前面。
java实现第一趟排序:
  public class QuickSort {
  public static void method(int[] array )
  {
  int i = 0 ;
  int j = array.length - 1;
  int k = array[0];
  while(i != j)
  {
  while(array[j] > k)
  {
  j--;
  }
  int temp = k;
  k = array[j];
  array[j] = temp;
  while (array[i] < k)
  {
  i++;
  }
  int temp1= k;
  k = array[i];
  array[i] = temp1;
  }
  if(k == array[j])
  {
  }
  }
  public static void main(String[] args)
  {
  int[] array = {49,38,65,97,76,13,27 };
  QuickSort.method(array);
  for(int i = 0; i < array.length; i++)
  {
  System.out.print(array[i] + " ");
  }
  }
  }
  运行结果:27 38 13 49 76 97 65快速排序就是递归调用此过程——在以49为中点分割这个数据序列,分别对前面一部分和后面一部分进行类似的快速排序,从而完成全部数据序列的快速排序,最后把此数据序列变成一个有序的序列,根据这种思想对于上述数组A的快速排序的全过程如图6所示:初始状态 {49 38 65 97 76 13 27} 进行一次快速排序之后划分为 {27 38 13} 49 {76 97 65} 分别对前后两部分进行快速排序 {27 38 13} 经第三步和第四步交换后变成 {13 27 38} 完成排序。{76 97 65} 经第三步和第四步交换后变成 {65 76 97} 完成排序

引用:http://baike.baidu.com/view/115472.htm

快速排序是对冒泡排序的一种改进。它的基本思想是:通过一躺排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一不部分的所有数据都要小,然后再按次方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。

    假设要排序的数组是A[1]……A[N],首先任意选取一个数据(通常选用第一个数据)作为关键数据,然后将所有比它小的数都放到它前面,所有比它大的数都放到它后面,这个过程称为一躺快速排序。一躺快速排序的算法是:

   1)、设置两个变量I、J,排序开始的时候I:=1,J:=N;

   2)以第一个数组元素作为关键数据,赋值给X,即X:=A[1];

   3)、从J开始向前搜索,即由后开始向前搜索(J:=J-1),找到第一个小于X的值,两者交换;

   4)、从I开始向后搜索,即由前开始向后搜索(I:=I+1),找到第一个大于X的值,两者交换;

   5)、重复第3、4步,直到I=J;

   例如:待排序的数组A的值分别是:(初始关键数据X:=49)

                   A[1]     A[2]     A[3]     A[4]     A[5]      A[6]     A[7]:

                     49        38       65       97       76       13        27

进行第一次交换后:   27        38       65       97       76       13        49

                   ( 按照算法的第三步从后面开始找

进行第二次交换后:   27        38       49       97       76       13        65

                  ( 按照算法的第四步从前面开始找>X的值,65>49,两者交换,此时I:=3 )

进行第三次交换后:   27        38       13       97       76       49        65

( 按照算法的第五步将又一次执行算法的第三步从后开始找

进行第四次交换后:   27        38       13       49       76       97        65

( 按照算法的第四步从前面开始找大于X的值,97>49,两者交换,此时J:=4 )

      此时再执行第三不的时候就发现I=J,从而结束一躺快速排序,那么经过一躺快速排序之后的结果是:27        38       13       49       76       97        65,即所以大于49的数全部在49的后面,所以小于49的数全部在49的前面。

      快速排序就是递归调用此过程——在以49为中点分割这个数据序列,分别对前面一部分和后面一部分进行类似的快速排序,从而完成全部数据序列的快速排序,最后把此数据序列变成一个有序的序列,根据这种思想对于上述数组A的快速排序的全过程如图6所示:

初始状态                        {49     38     65     97     76     13     27}  

进行一次快速排序之后划分为      {27     38     13}     49   {76     97     65}

分别对前后两部分进行快速排序    {13}    27    {38}

                                结束         结束    {49    65}    76    {97}

                                                    49   {65}         结束

                                                        结束

                          图6    快速排序全过程

1)、设有N(假设N=10)个数,存放在S数组中;

2)、在S[1。。N]中任取一个元素作为比较基准,例如取T=S[1],起目的就是在定出T应在排序结果中的位置K,这个K的位置在:S[1。。K-1]<=S[K]<=S[K+1..N],即在S[K]以前的数都小于S[K],在S[K]以后的数都大于S[K];

3)、利用分治思想(即大化小的策略)可进一步对S[1。。K-1]和S[K+1。。N]两组数据再进行快速排序直到分组对象只有一个数据为止。

如具体数据如下,那么第一躺快速排序的过程是:

数组下标: 1      2      3      4      5      6      7      8      9      10

           45     36     18     53     72     30     48     93     15      36

      I                                                                   J

(1)      36     36     18     53     72     30     48     93     15      45

      

(2)      36     36     18     45     72     30     48     93     15      53

(3)      36     36     18     15     72     30     48     93     45      53

(4)      36     36     18     15     45     30     48     93     72      53

(5)      36     36     18     15     30     45     48     93     72      53

通过一躺排序将45放到应该放的位置K,这里K=6,那么再对S[1。。5]和S[6。。10]分别进行快速排序。

一般来说,冒泡法是程序员最先接触的排序方法,它的优点是原理简单,编程实现容易,但它的缺点就是--程序的大忌--速度太慢。下面我介绍一个理解上简单但编程实现上不是太容易的排序方法,我不知道它是不是现有排序方法中最快的,但它是我见过的最快的。排序同样的数组,它所需的时间只有冒泡法的 4% 左右。我暂时称它为“快速排序法”。

     “快速排序法”使用的是递归原理,下面我结合一个例子来说明“快速排序法”的原理。首先给出一个数组{53,12,98,63,18,72,80,46, 32,21},先找到第一个数--53,把它作为中间值,也就是说,要把53放在一个位置,使得它左边的值比它小,右边的值比它大。{21,12,32, 46,18,53,80,72,63,98},这样一个数组的排序就变成了两个小数组的排序--53左边的数组和53右边的数组,而这两个数组继续用同样的方式继续下去,一直到顺序完全正确。

     我这样讲你们是不是很胡涂,不要紧,我下面给出实现的两个函数:

/*
n就是需要排序的数组,left和right是你需要排序的左界和右界,
如果要排序上面那个数组,那么left和right分别是0和9
*/

void quicksort(int n[], int left,int right)
{
int dp;
if (left<right) {

     /*
     这就是下面要讲到的函数,按照上面所说的,就是把所有小于53的数放
     到它的左边,大的放在右边,然后返回53在整理过的数组中的位置。
     */
     dp=partition(n,left,right);

     quicksort(n,left,dp-1);

     quicksort(n,dp+1,right); //这两个就是递归调用,分别整理53左边的数组和右边的数组
}
}

     我们上面提到先定位第一个数,然后整理这个数组,把比这个数小的放到它的左边,大的放右边,然后

返回这中间值的位置,下面这函数就是做这个的。
int partition(int n[],int left,int right)
{
int lo,hi,pivot,t;

pivot=n[left];
lo=left-1;
hi=right+1;

while(lo+1!=hi) {
     if(n[lo+1]<=pivot)
       lo++;
     else if(n[hi-1]>pivot)
       hi--;
     else {
       t=n[lo+1];
       n[++lo]=n[hi-1];
       n[--hi]=t;
     }
}

n[left]=n[lo];
n[lo]=pivot;
return lo;
}

     这段程序并不难,应该很好看懂,我把过程大致讲一下,首先你的脑子里先浮现一个数组和三个指针,第一个指针称为p指针,在整个过程结束之前它牢牢的指向第一个数,第二个指针和第三个指针分别为lo指针和hi指针,分别指向最左边的值和最右边的值。lo指针和hi指针从两边同时向中间逼近,在逼近的过程中不停的与p指针的值比较,如果lo指针的值比p指针的值小,lo++,还小还++,再小再++,直到碰到一个大于p指针的值,这时视线转移到hi指针,如果 hi指针的值比p指针的值大,hi--,还大还--,再大再--,直到碰到一个小于p指针的值。这时就把lo指针的值和hi指针的值做一个调换。持续这过程直到两个指针碰面,这时把p指针的值和碰面的值做一个调换,然后返回p指针新的位置。

#include<iostream>
using namespace std;
int a[200001],n;
void swap(int &a,int &b){
int tmp = a;
a = b;
b = tmp;
}
int partition(int p,int r){
int rnd = rand()%(r-p+1)+p;
swap(a[rnd],a[r]);
int pvt = r, i = p-1;
for(int j = i+1;j<r;j++)
if(a[j]<a[pvt])
swap(a[j],a[++i]);
swap(a[++i],a[pvt]);
return i;
}
void qsort(int p,int r){
if(p<r){
int q = partition(p,r);
qsort(p,q-1);
qsort(q+1,r);
}
}

交换排序:
思想:所谓交换,就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置,交换排序的特点是:将键值较大的记录向序列的尾部移动,键值较小的记录向序列的前部移动。
Java代码 
public static void exchangeSort(int[] arr) { 
       for (int i = 0; i < arr.length - 1; i++) { 
           for (int j = i + 1; j < arr.length; j++) { 
              if (arr[i] > arr[j]) { 
                  int temp = arr[i]; 
                  arr[i] = arr[j]; 
                  arr[j] = temp; 
              } 
           } 
       } 
    } 
int main(){
cin>>n;
for(int i=0;i<n;i++)
cin>>a[i];
qsort(0,n-1);
for(int i=0;i<n;i++)
cout<<a[i];
return 0;
}
分享到:
评论

相关推荐

    C语言实现快速排序算法(含实现步骤)

    快速排序是一种非常高效的排序算法,它的基本原理是采用分治策略。以下是快速排序的原理和实现步骤: 原理: 1、选择一个基准值。 2、通过一趟排序将待排序的序列分割成独立的两部分,其中一部分的所有数据都比另一...

    C/C++实现双路快速排序算法原理

    本文实例为大家分享了C/C++实现双路快速排序算法的具体代码,供大家参考,具体内容如下 看了刘宇波的视频,讲双路快速排序的,原理讲的很直观,程序讲解也一看就懂。这里写一下自己的理解过程,也加深一下自己的理解...

    C/C++实现三路快速排序算法原理

    书接上文,上次讲到了双路快速排序,双路快速排序是将等于v(标志数)的数也进行交换,从而避免了在处理有大量重复数据的数组分组时的不平衡。而三路快速排序则是将等于v的数也分成一组,同样可以解决上述问题。其...

    排序算法原理与实现[冒泡、选择、插入、快速、哈希、计数](python版)

    冒泡排序算法的基本原理就是比较相邻两个数字的大小。将两个数中比较大的那个数交换到靠后的位置,不断交换下去就可以将最大的那两个数放到队列的尾部。然后重头再次交换)(交换list.lenght-1次),直到将数列排成有序...

    C++大作业4种排序算法演示.docx

    4.快速排序原理:通过一趟排序将要排序的记录分割成独立的两部分,其中一部分的所有记录关键码比另一部分的都小,再按此方法对两部分数据进行递归,实现快速排序。 算法实现:从每趟数据的左边界向右搜索一个比它大...

    js实现数组冒泡排序、快速排序原理

    本文为大家分享了js数组冒泡排序、快速排序的实现原理,供大家参考,具体内容如下 1、冒泡排序:  随便从数组中拿一位数和后一位比较,如果是想从小到大排序,那么就把小的那一位放到前面,大的放在后面,简单来说...

    Go语言实现冒泡排序、选择排序、快速排序及插入排序的方法

    本文实例讲述了Go语言实现冒泡排序、选择排序、快速排序及插入排序的方法。分享给大家供大家参考。具体分析如下: 算法是程序的灵魂,而排序算法则是一种最基本的算法。排序算法有许多种,这里介绍4中排序算法:冒泡...

    选择排序——Java实现

    冒泡排序实际上是将数据从右至左排序完成(从右至左、从大到小进行交换排序),而快速排序是将数据从左到右排序完成(从左至右、从小到大进行交换排序),虽然选择排序相对于冒泡排序将交换次数从O(n2)O(n^2)O(n2)...

    排序算法的javascript实现与讲解(99js手记)

    插入排序,选择排序,快速排序,冒泡排序都是比较排序 思路 依次比较相邻的两个数,将小数放在前面,大数放在后面。 step1:比较第1个和第2个数,将小数放前,大数放后。比较第2个数和第3个数,将小数放前,大数放后...

    C语言下的冒泡排序,可以直接编译使用

    这个C语言程序主要实现了一...总之,这个C语言程序简单地实现了冒泡排序算法,包括交换元素的swap函数和实际排序过程的bubble_sort函数。代码中的注释说明了程序的结构和关键部分,有助于用户快速理解程序的工作原理。

    15.链表.wmv(目前数据结构最好的视频,共42集,需要哪一集的知识自己下,一集3积分)

    C++实现 数据结构与算法视频教程 01交换算法 02冒泡排序 03选择排序 04顺序排序 05折半排序 06递归算法 07递归折半查找 08算法_perm 09插入排序 10快速排序 11归并排序 12顺序栈 13顺序队列 14链表的基本概率 15...

    Leetcode扑克-MyDataStruct:数据结构学习记录

    排序算法 选择排序 简单选择排序 堆排序 交换排序 冒泡排序 快速排序 插入排序 直接插入排序 折半插入排序 表插入排序 希尔排序(增量递减排序) 归并排序 tree.impl 二叉树的前、中、后序、层次遍历,二叉树的深度,...

    美国..现代编译原理C语言描述.高清版

    11.4 图着色的实现 175 11.4.1 传送指令工作表的管理 176 11.4.2 数据结构 176 11.4.3 程序代码 177 11.5 针对树的寄存器分配 181 程序设计:图着色 184 推荐阅读 185 习题 185 第12章 整合为一体 188 程序设计:...

    Algorithm Design(英文版)

    5.1 第一个递推式:归并排序算法 5.2 更多的递推关系 5.3 计数逆序 5.4 找最接邻近的点对 5.5 整数乘法 5.6 卷积与快速傅里叶变换 带解答的练习 练习 注释和进一步的阅读 第6章 动态规划 6.1 带权的区间调度:一个...

    java 面试题 总结

    Collections是针对集合类的一个帮助类,他提供一系列静态方法实现对各种集合的搜索、排序、线程安全化等操作。 10、&和&&的区别。 &是位运算符,表示按位与运算,&&是逻辑运算符,表示逻辑与(and)。 11、HashMap...

    超级有影响力霸气的Java面试题大全文档

    Collections是针对集合类的一个帮助类,他提供一系列静态方法实现对各种集合的搜索、排序、线程安全化等操作。 13、&和&&的区别。 &是位运算符,表示按位与运算,&&是逻辑运算符,表示逻辑与(and)。 14、...

    C/C++程序员面试指南.杨国祥(带详细书签).pdf

    还介绍了排序算法及数据结构的实现,包括链表、堆栈、队列和树。此外,本书开始用两章篇幅详细介绍了中英文面试的注意事项、常见问题及程序员的职业规划等软件工程师的常识。最后四章详细讲解了现在流行的智力测试题...

    操作系统原理 计算机

    1.4.6 操作系统功能的实现模型...............................................................................................35 1.4.7 实例研究:Windows 2000/XP 客户/服务器结构..............................

    JAVA上百实例源码以及开源项目源代码

     Java实现的FTP连接与数据浏览程序,实现实例化可操作的窗口。  部分源代码摘录:  ftpClient = new FtpClient(); //实例化FtpClient对象  String serverAddr=jtfServer.getText(); //得到服务器地址  ...

    JAVA上百实例源码以及开源项目

    百度云盘分享 ... Java实现的FTP连接与数据浏览程序,实现实例化可操作的窗口。  部分源代码摘录:  ftpClient = new FtpClient(); //实例化FtpClient对象  String serverAddr=jtfServer.getText();...

Global site tag (gtag.js) - Google Analytics