C程序实现快速排序算法

Myth丶恋晨 2023-03-05 15:51 11阅读 0赞

**Quick Sort** is an algorithm based on the divide and conquers paradigm wherein the problem is solved by dividing it into subproblems and then combining the results of each subproblem. Unlike [Merge Sort][], where the array is divided using the middle element only, here the array divided using a pivot element. This pivot element may be an element of the array-like first, last, middle, or random.

**快速排序**是一种基于分而治之范式的算法，其中，通过将问题分为子问题然后合并每个子问题的结果来解决问题。 与“ [合并排序”][Merge Sort]不同，“ [合并排序”][Merge Sort]仅使用中间元素对数组进行分割，而此处使用“透视”元素对数组进行分割。 该枢轴元素可以是阵列状的第一，最后，中间或随机元素。

The default implementation of **Quick Sort** is unstable and in-place.

**快速排序**的默认实现是不稳定且就地的。

**Quick Sort** calls two functions in its implementation. One is the *QuickSort()* wherein it recursively calls itself for division purpose and the other is *Partition()* which is used to determine the pivot element around which the division of array takes place. This pivot element is placed at its correct position in the sorted array where the elements at its left are smaller than it and elements at its right are higher than it. The two sub-lists go through the same process again.

**快速排序**在其实现中调用了两个函数。 一个是*QuickSort()，*其中它以除法为目的递归地调用自身，另一个是*Partition()* ，用于确定围绕数组进行除法的枢轴元素。 该枢轴元素被放置在排序数组中其正确位置，在该数组中，左侧的元素小于其，右侧的元素高于其。 这两个子列表再次经过相同的过程。

**Pseudo code for QuickSort() and Partition():**

**QuickSort()和Partition()的伪代码：**

Quick_Sort(arr[], low, high)
    {
    If high > low:
       q = partition(arr, low, high) // index of pivot element 
       
       Quick_Sort(arr, low, q - 1)
       Quick_Sort(arr, q + 1, high) 
    
    end if
    }
    
    
    Partition(arr[], low, high)
    {
       pivot = arr[high] //considering last element as pivot
       
       i = low – 1
       for j -> low to high-1:
          if arr[j] < pivot:
             i++
             swap arr[i] and arr[j]
          end if
       end for
       
       swap arr[i + 1] and arr[high]
       return (i+1) 
    }

**Example:**

**例：**

**Input Array:**  
10, 80, 30, 90, 40, 70** **

**输入数组：**   
 10、80、30、90、40、70 ** **

**1st call for partition:**

**第一次分区调用：**

Low = 0, high = 5, pivot = arr \[high\] = 70, i = -1  
Traverse j from low to high – 1:

低= 0，高= 5，枢轴= arr \[高\] = 70，i = -1  
从低到高遍历j – 1：

For j = 0,

对于j = 0，

1.  arr\[j\] < pivot, therefore, i++ and swap(arr\[i\], arr\[j\])
    
    arr \[j\] <枢纽，因此，i ++和swap(arr \[i\]，arr \[j\])
2.  Now, **i = 0**
    
    现在， **我= 0**
3.  Arr\[\] = **10** 80 30 90 40 70
    
    Arr \[\] = **10** 80 30 90 40 70

For j = 1,

对于j = 1，

1.  Arr\[j\] > pivot, move forward
    
    Arr \[j\]>旋转，向前移动

For j = 2,

对于j = 2，

1.  Arr\[j\] < pivot, therefor i++ and swap (arr\[i\], arr\[j\])
    
    Arr \[j\] <枢纽，因此可以进行i ++和交换(arr \[i\]，arr \[j\])
2.  Now, i = 1
    
    现在，我= 1
3.  Arr\[\] = 10 **30** 80 90 40 70
    
    Arr \[\] = 10 **30** 80 90 40 70

For j = 3,

对于j = 3，

1.  Arr\[j\] > pivot, move forward
    
    Arr \[j\]>旋转，向前移动

For j = 4,

对于j = 4，

1.  Arr\[j\] < pivot, therefor i++ and swap (arr\[i\], arr\[j\])
    
    Arr \[j\] <枢纽，因此可以进行i ++和交换(arr \[i\]，arr \[j\])
2.  Now, i = 2
    
    现在，我= 2
3.  Arr\[\] = 10 30 **40** 90 80 70
    
    Arr \[\] = 10 30 **40** 90 80 70

After coming out of for loop:

在退出for循环之后：

1.  Swap arr\[i+1\] and arr\[high\]
    
    交换arr \[i + 1\]和arr \[high\]
2.  Arr\[\] = 10 30 40 **70** 80 90
    
    Arr \[\] = 10 30 40 **70** 80 90
3.  Return i + 1, therefore, return index of 70 which is i = 3 as 70 is the pivot element.
    
    因此，返回i + 1，返回索引70(即i = 3，因为70是枢轴元素)。

Similarly, the two sub lists before 70 and after 70 will be passed for sorting.

同样，将传递70之前和70之后的两个子列表进行排序。

We can see that all the elements to the left of 70 are smaller than 70 and all to the right are greater than it. In our example, the two sub lists are already sorted, but when we run the algorithm, the two sub lists would be passed for sorting until each sub list contains exactly one element and hence, is sorted.

我们可以看到70左边的所有元素都小于70，而所有右边的元素都大于70。 在我们的示例中，两个子列表已经被排序，但是当我们运行算法时，两个子列表将被传递以进行排序，直到每个子列表仅包含一个元素并因此被排序。

**Time Complexity:**

**时间复杂度：**

The time complexity of the **Quick Sort** algorithm can be defined by the following recurrence relation for the best and average case only and can be solved by Master’s method:

**快速排序**算法的时间复杂度只能由以下递归关系定义，仅适用于最佳情况和平均情况，并且可以通过Master方法解决：

1.  T (n) = T (n/2) + Ɵ(n)
    
    T(n)= T(n / 2)+Ɵ(n)
2.  Worst Case = O(N^2)
    
    最坏的情况= O(N ^ 2)

When the pivot is the smallest or the largest element. When the list is already sorted in either ascending or descending order and we choose the last element as pivot, the worst case will occur. The sublist will consist of n-1 elements after **Partition( )** as the chosen pivot was already at its correct position. As a result, the recurrence relation changes to –

当枢轴是最小或最大元素时。 当列表已经按照升序或降序排序并且我们选择最后一个元素作为枢轴时，最坏的情况就会发生。 子列表将由**Partition()**之后的n-1个元素组成，因为选定的枢轴已经在其正确位置。 结果，递归关系变为–

1.  T (n) = T (n-1) + Ɵ(n)
    
    T(n)= T(n-1)+Ɵ(n)
2.  Average Case = Ɵ(N log N)
    
    平均情况=Ɵ(N log N)
3.  Best Case = Ω(N log N), when the partition takes place at the middle element always
    
    最佳情况=Ω(N log N)，当分区总是在中间元素处发生时
4.  Space Complexity: Ɵ(N)
    
    空间复杂度：Ɵ(N)

**Quick Sort Implementation:**

**快速排序实施：**

#include <stdio.h>
    
    void swap(int* a, int* b)
    {
        int temp = *a;
        *a = *b;
        *b = temp;
    }
    
    int partition(int arr[], int low, int high)
    {
        int pivot = arr[high];
        int i = low - 1;
        for (int j = low; j <= high - 1; j++) {
            if (arr[j] < pivot) {
                i++;
                swap(&arr[i], &arr[j]);
            }
        }
        swap(&arr[i + 1], &arr[high]);
        return (i + 1);
    }
    
    void quick_sort(int arr[], int low, int high)
    {
        if (low < high) {
            int q = partition(arr, low, high);
    
            quick_sort(arr, low, q - 1);
            quick_sort(arr, q + 1, high);
        }
    }
    
    int main()
    {
        int arr[] = { 10, 80, 30, 90, 40, 50, 70 };
        int n = sizeof(arr) / sizeof(arr[0]);
    
        printf("After performing quick sort:\n");
        for (int i = 0; i < n; i++) {
            printf("%d ", arr[i]);
        }
        
        quick_sort(arr, 0, n - 1);
    
        printf("\nAfter performing quick sort:\n");
        for (int i = 0; i < n; i++) {
            printf("%d ", arr[i]);
        }
        
        return 0;
    }

**Output:**

**输出：**

After performing quick sort:
    10 80 30 90 40 50 70
    After performing quick sort:
    10 30 40 50 70 80 90

Although the worst case of **quick sort** is **O (N^2)**, it can be optimized with the choice of the pivot element so that the worst-case never occurs. There can be many variants of quick sort.

尽管**快速排序**的最坏情况是**O(N ^ 2)** ，但可以通过选择枢轴元素来优化它，从而永远不会发生最坏情况。 快速排序可以有多种变体。

It is a cache-friendly algorithm and is tail-recursive.

这是一种缓存友好的算法，并且是尾递归的。

> 翻译自: [https://www.includehelp.com/c-programs/implement-quick-sort-algorithm.aspx][https_www.includehelp.com_c-programs_implement-quick-sort-algorithm.aspx]

[Merge Sort]: https://www.includehelp.com/c-programs/implement-merge-sort-algorithm.aspx
[https_www.includehelp.com_c-programs_implement-quick-sort-algorithm.aspx]: https://www.includehelp.com/c-programs/implement-quick-sort-algorithm.aspx