首页 > 代码库 > 常用排序算法之——快速排序

常用排序算法之——快速排序

2024-07-17 01:19:47   222人阅读

快速排序的原理：

首先找一个标兵值，等于某一个元素值；遍历数组，将数组分为小于标兵值和大于标兵值的两部分；然后分别对两个部分采用快速排序，递归。

 

分开数组时，维持一个指针，指向已找到小部分的最后一个元素；一个指针用于遍历。

 

不稳定排序算法。当数组已经有序时，时间复杂度最差，为O(N2)，平均、最优情况下都为O(N lgN)。

 

代码如下：

 1 #include <iostream> 2 using namespace std; 3  4 template<typename T> 5 void quickSort(T num[], int first, int last) 6 { 7     if(first >= last) 8         return; 9 10     T pviot = num[first];11 12     int small = first;  //指针，指向已经处理过的小部分的最后一个值13 14     for(int i = first + 1; i <= last; ++i)15     {16         if(num[i] <= pviot)17         {18             ++small;  //将小部分后第一个值和找到的小于标兵的值交换19             if(small < i)20             {21                 swap(num[small], num[i]);22             }23         }24     }25 26     swap(num[first], num[small]);27 28     quickSort(num, first,     small - 1);29     quickSort(num, small + 1, last);30 }31 32 int main()33 {34     const int n = 5;35 36     int    ia[n] = {1, 3, 6, 2, 4};37     double da[n] = {1.2, 3.4, 6.7, 2.3, 4.5};38 39     quickSort(ia, 0, n - 1);40     quickSort(da, 0, n - 1);41 42     for(int i = 0; i < n; ++i)43         cout << ia[i] << ‘ ‘;44     cout << endl;45 46     for(int i = 0; i < n; ++i)47         cout << da[i] << ‘ ‘;48     cout << endl;49 50     return 0;51 }

 


联系
我们