C ++程序使用随机化实现快速排序

2024-04-22 16:58:13 17

快速排序技术是通过将列表分为两部分来完成的。最初，枢轴元素是通过分区算法选择的。枢轴的左侧部分保留的值小于枢轴，右侧部分保留较大的值。分区后，将使用相同的过程对每个单独的列表进行分区。

在这种情况下，我们将随机选择枢轴元素。选择枢轴后，我们进行分区，然后递归对数组进行排序。

快速排序技术的复杂性

时间复杂度-O（nlogn）为最佳情况和平均情况，O（n²）为最坏情况。

空间复杂度-O（logn）

输入 -未排序列表：904522112250
输出 -排序后的数组：112222455090

算法

分区（数组，下，上）

输入-数据集数组，下边界和上边界

输出-枢轴位于正确的位置

Begin
   index := lower
   pivot := higher
   for i in range lower to higher, do
      if array[i] < array[pivot], then
         exchange the values of array[i] and array[index]
         index := index + 1
   done
   exchange the values of array[pivot] and array[index]
End

random_pivot_partition（数组，较低，较高）

输入-数据集数组，下边界和上边界

输出-随机选择的枢轴的最终索引

Begin
   n := a random number
   pvt := lower + n mod (upper – lower + 1)
   exchange the values of array[pivot] and array[upper]
   index := Partition(array, lower, upper)
   return index
End

quickSort(array,left,right)

输入-数据数组以及数组的上下限

输出-排序的数组

Begin
   if lower < right then
      q = random_pivot_partition(array, left, right).
      quickSort(array, left, q-1)
      quickSort(array, q+1, right)
End

范例程式码

#include<iostream>
#include<cstdlib>
#include<ctime>
#define MAX 100
using namespace std;
void random_shuffle(int arr[]) {
   //将数组元素随机排列到随机位置的功能
   srand(time(NULL));
   for (int i = MAX - 1; i > 0; i--) {
      int j = rand()%(i + 1);
      int temp = arr[i];
      arr[i] = arr[j];
      arr[j] = temp;
   }
}
//根据作为枢轴值的高值对数组进行分区。
int Partition(int a[], int low, int high) {
   int pivot, index, i;
   index = low;
   pivot = high;
   for(i=low; i < high; i++) {
      //寻找枢轴索引。
      if(a[i] < a[pivot]) {
         swap(a[i], a[index]);
         index++;
      }
   }
   swap(a[pivot], a[index]);
   return index;
}
int RandomPivotPartition(int a[], int low, int high){
   //枢轴的随机选择。
   int pvt, n, temp;
   n = rand();
   pvt = low + n%(high-low+1); // Randomizing the pivot value from sub-array.
   swap(a[high], a[pvt]);
   return Partition(a, low, high);
}
void quick_sort(int arr[], int p, int q) {
   //对列表进行递归排序
   int pindex;
   if(p < q) {
      pindex = RandomPivotPartition(arr, p, q); //randomly choose pivot
      //递归地实现QuickSort。
      quick_sort(arr, p, pindex-1);
    quick_sort(arr, pindex+1, q);
}
}
int main() {
int i;
int arr[MAX];
for (i = 0;i < MAX; i++)
arr[i] = i + 1;
random_shuffle(arr); //To randomize the array
quick_sort(arr, 0, MAX - 1); //sort the elements of array
for (i = 0; i < MAX; i++)
cout << arr[i] << " ";
cout << endl;
return 0;
}

输出结果

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 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100