前两天,亲爱的KC童鞋问了我关于快速排序的问题,可惜我忘得差不多了,没帮上什么忙,惭愧惭愧。于是就潜心的复习了一下快速排序的算法。

维基百科上,关于快排的定义是这样的:

快速排序使用分治法(Divide and conquer)策略来把一个序列(list)分为两个子序列(sub-lists)。

步骤为:

  1. 从数列中挑出一个元素,称为 “基准”(pivot),
  2. 重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。在这个分割之后,该基准是它的最后位置。这个称为分割(partition)操作。
  3. 递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序。

通俗的说,就是对于一个数组arr[n],第一次取arr[0]为基准,数组中其他所有比arr[0]小的元素移动到arr的左半边,所有比arr[0]大的移动到arr右半边,最后把arr[0]放在“中间”(此处中间实际上就是分割点,不一定正好在数组的中间位置)。并且把原数组分为两个,即一个比“基准”(这里假设第一次arr[0],其实可以任意元素)大,另一个比“基准”小。之后递归,知道排序完成。

例如数组    arr[5]={ 8,3,7,5,9}

经过第一次排序后就成了 3,7,5,8,9    并且形成了两个新数组  3,7,5    和    8,9

其次要注意的,在形成新数组的时候,可以另外开辟单元储存,也可以在原数组储存。前者空间复杂度为较高(具体各为多少?那位同学告诉我?)

所以我先写了用另外数组储存的,后写了原数组存储的。

原数组存储代码

001 #include <iostream>
002 #include<stdlib.h>
003 #define n 18
004 using namespace std;
005 
006 void swap(int *a,int *b)
007 {
008      int t=*a;
009      *a=*b;
010      *b=t;
011 }
012 
013 void quicksort(int arr[],int beg,int end)
014 {
015      int temp;
016     if(beg<end&&beg+1!=end)
017     {
018 
019          int b,e;
020          b=beg+1;
021          e=end;
022          while(b<=e)
023          {
024                  if(arr[b]<=arr[b1])
025                  {
026                      swap(&arr[b],&arr[b1]);
027                      b++;
028                  }
029                  else
030                  {
031                      swap(&arr[b],&arr[e]);
032                      e;
033                  }
034          }
035 
036         quicksort(arr,beg,b1);//递归
037         quicksort(arr,b,end);
038 
039      }
040      else if(beg+1==end)
041      {
042           if(arr[beg]>arr[end])
043           {
044                swap(&arr[beg],&arr[end]);
045 
046           }
047           quicksort(arr,0,0);
048           quicksort(arr,0,0);
049      }
050      else
051          return ;
052 }
053 
054 
055 int main()
056 {
057 
058     int arr[n]={9,7,8,3,5,7,5,2,1,6,9,14,12,2,18,45,16,8};
059 
060     for(int i=0;i<n;i++)
061     cout<<arr[i]<<“,”;
062     cout<<endl;
063 
064     quicksort(arr,0,n1);
065 
066     for(int i=0;i<n;i++)
067     cout<<arr[i]<<“,”;
068 
069     system(“pause”);
070     return 0;
071 }
072 
073 
074 //额外空间存储的代码
075 
076 void quicksort(int arr[],int temp[],int beg,int end)
077 {
078     if(beg<end&&beg+1!=end)
079     {
080 
081          int b,e,bb,ee;
082          int pivot=arr[beg];
083          b=beg;bb=beg;
084          e=end;ee=end;
085          bb++;
086          while(bb<=ee)
087          {
088                  if(arr[bb]<pivot)
089                  {
090                      temp[b++]=arr[bb++];
091                  }
092                  else
093                  {
094                      temp[e]=arr[bb++];
095                  }
096          }
097         temp[b]=pivot;
098 
099         for(int i=beg;i<=end;i++)
100         arr[i]=temp[i];
101 
102         quicksort(arr,temp,beg,b);
103         quicksort(arr,temp,b+1,end);
104      }
105      else if(beg+1==end)
106      {
107           if(arr[beg]>arr[end])
108           {
109                int t=arr[beg];
110                arr[beg]=arr[end];
111                arr[end]=t;
112           }
113           quicksort(arr,temp,0,0);
114           quicksort(arr,temp,0,0);
115      }
116      else
117          return ;
118 
119 }
Tags: ,,,. 5,521 views
Home

3 Comments so far

Trackbacks/Pingbacks

Leave a comment

Name(required)
Mail (required),(will not be published)
Website(recommended)

Fields in bold are required. Email addresses are never published or distributed.

Some HTML code is allowed:
<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>
URLs must be fully qualified (eg: http://blog.nlogn.cn),and all tags must be properly closed.

Line breaks and paragraphs are automatically converted.

Please keep comments relevant. Off-topic, offensive or inappropriate comments may be edited or removed.