首页 > 代码库 > 快速排序2

快速排序2

2024-09-29 14:51:39   215人阅读

算法：

1、从数列中挑出一个元素，称为 "基准"（pivot），

2、重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。

3、递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。

07.void QuickSort(int *arr, int left, int right)  
08.{  
09.  int i,j;  
10.  if(left<right)  
11.  {  
12.    i=left;j=right;  
13.    arr[0]=arr[i]; //准备以本次最左边的元素值为标准进行划分，先保存其值  
14.    do  
15.    {  
16.      while(arr[j]>arr[0] && i<j)   
17.        j--;        //从右向左找第1个小于标准值的位置j  
18.      if(i<j)                               //找到了，位置为j  
19.      {   
20.        arr[i] = arr[j];  
21.        i++;  
22.      }           //将第j个元素置于左端并重置i  
23.      while(arr[i]<arr[0] && i<j)  
24.        i++;      //从左向右找第1个大于标准值的位置i  
25.      if(i<j)                       //找到了，位置为i  
26.      {   
27.        arr[j] = arr[i];  
28.        j--;  
29.      }           //将第i个元素置于右端并重置j  
30.    }while(i!=j);  
31.    arr[i] = arr[0];         //将标准值放入它的最终位置,本次划分结束  
32.    quicksort(arr, left, i-1);     //对标准值左半部递归调用本函数  
33.    quicksort(arr, i+1, right);    //对标准值右半部递归调用本函数  
34.  }  
35.}

 

快速排序2


联系
我们