快速排序的基本思想与代码实现

客官°小女子只卖身不卖艺 2022-05-29 08:41 154阅读 0赞

# 快速排序的基本思想与代码实现 #

## 一、思想 ##

1，先选一个“标尺”，我们通常选左边第一个  
2，用它把整个队列过一遍筛子，  
3，以保证：其左边的元素都不大于它，其右边的元素都不小于它。  
4，这样，排序问题就被分割为两个子区间。

5，再分别对子区间排序就可以了。

## 二、代码 ##

C++ Code

<table style="font-family:Consolas, 'Courier New';font-size:12px;vertical-align:text-top;line-height:15px;"> 
 <tbody> 
 <tr> 
 <td style="color:#008284;background-color:#e3e3e3;vertical-align:text-top;"> 
 <div style="margin:7px;text-align:right;white-space:nowrap;">
 1 
 2 
 3 
 4 
 5 
 6 
 7 
 8 
 9 
 10 
 11 
 12 
 13 
 14 
 15 
 16 
 17 
 18 
 19 
 20 
 21 
 22 
 23 
 24 
 25 
 26 
 27 
 28 
 29 
 30 
 31 
 32 
 33 
 34 
 35 
 36 
 37 
 38 
 39 
 40 
 41 
 42 
 43 
 44 
 45 
 46 
 47 
 48 
 49 
 50 
 51 
 52 
 53 
 54 
 
 </div></td> 
 <td style="background-color:#008284;padding:1px;"> 
 <div style="border:1px #008284 solid;"></div></td> 
 <td style="background-color:#efefef;width:100%;vertical-align:text-top;color:#000000;"> 
 <div style="margin:7px;"> 
 #include&nbsp;&lt;stdio.h&gt; 
 
 
 void&nbsp;swap( 
 int&nbsp;a[],&nbsp; 
 int&nbsp;i,&nbsp; 
 int&nbsp;j) 
 { 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 int&nbsp;t&nbsp;=&nbsp;a[i]; 
 &nbsp;&nbsp;&nbsp;&nbsp;a[i]&nbsp;=&nbsp;a[j]; 
 &nbsp;&nbsp;&nbsp;&nbsp;a[j]&nbsp;=&nbsp;t; 
 } 
 
 
 int&nbsp;partition( 
 int&nbsp;a[],&nbsp; 
 int&nbsp;p,&nbsp; 
 int&nbsp;r) 
 { 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 int&nbsp;i&nbsp;=&nbsp;p; 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 int&nbsp;j&nbsp;=&nbsp;r&nbsp;+&nbsp; 
 1; 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 int&nbsp;x&nbsp;=&nbsp;a[p]; 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 while( 
 1) 
 &nbsp;&nbsp;&nbsp;&nbsp;{ 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 while(i&nbsp;&lt;&nbsp;r&nbsp;&amp;&amp;&nbsp;a[++i]&nbsp;&lt;&nbsp;x);&nbsp; 
 ///从左边找比标尺大的数 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 while(a[--j]&nbsp;&gt;&nbsp;x);&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 ///从右边找比标尺小的数 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 if(i&nbsp;&gt;=&nbsp;j)&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 ///当两个位置相等，表示已经全部找完 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 break; 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;swap(a,&nbsp;i,&nbsp;j); 
 &nbsp;&nbsp;&nbsp;&nbsp;} 
 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 ///扫描完成，枢轴到位 &nbsp;&nbsp;&nbsp;&nbsp;swap(a,&nbsp;p,&nbsp;j); 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 return&nbsp;j; 
 } 
 
 
 ///递归过程 
 void&nbsp;quicksort( 
 int&nbsp;a[],&nbsp; 
 int&nbsp;p,&nbsp; 
 int&nbsp;r) 
 { 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 if(p&nbsp;&lt;&nbsp;r) 
 &nbsp;&nbsp;&nbsp;&nbsp;{ 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 int&nbsp;q&nbsp;=&nbsp;partition(a,&nbsp;p,&nbsp;r); 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;quicksort(a,&nbsp;p,&nbsp;q&nbsp;-&nbsp; 
 1); 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;quicksort(a,&nbsp;q&nbsp;+&nbsp; 
 1,&nbsp;r); 
 &nbsp;&nbsp;&nbsp;&nbsp;} 
 } 
 
 
 int&nbsp;main() 
 { 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 int&nbsp;i; 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 int&nbsp;a[]&nbsp;=&nbsp;{ 
 5,&nbsp; 
 13,&nbsp; 
 6,&nbsp; 
 24,&nbsp; 
 2,&nbsp; 
 8,&nbsp; 
 19,&nbsp; 
 27,&nbsp; 
 6,&nbsp; 
 12,&nbsp; 
 1,&nbsp; 
 17}; 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 int&nbsp;N&nbsp;=&nbsp; 
 12; 
 
 &nbsp;&nbsp;&nbsp;&nbsp;quicksort(a,&nbsp; 
 0,&nbsp;N&nbsp;-&nbsp; 
 1); 
 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 for(i&nbsp;=&nbsp; 
 0;&nbsp;i&nbsp;&lt;&nbsp;N;&nbsp;i++) 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;printf( 
 "%d&nbsp;",&nbsp;a[i]); 
 &nbsp;&nbsp;&nbsp;&nbsp;printf( 
 "\n"); 
 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 return&nbsp; 
 0; 
 } 
 
 </div></td> 
 </tr> 
 </tbody> 
</table>