C语言简明讲解快速排序的应用

快速排序的概述

快速排序是一种基于比较的排序算法，最初由Tony Hoare于1959年发明，因其在实践中的高效性而受到广泛的应用。快速排序的基本思想是通过不断地分割（partition）和交换（swap）来实现排序，具体来说，就是先选取一个pivot数，然后将序列中小于pivot的数放在pivot左边，大于pivot的数放在pivot右边，最后对pivot左右两个子序列分别进行排序。

快速排序的实现

下面是快速排序的代码实现，在本例中选择数组的最后一个元素作为pivot数：

void quicksort(int *arr, int left, int right) {
  if (left < right) {
    int pivot = arr[right];
    int i = left - 1;
    for (int j = left; j <= right - 1; j++) {
      if (arr[j] < pivot) {
        i++;
        swap(arr+i, arr+j);
      }
    }
    swap(arr+i+1, arr+right);
    int mid = i+1;
    quicksort(arr, left, mid-1);
    quicksort(arr, mid+1, right);
  }
}

void swap(int *a, int *b) {
  int t = *a;
  *a = *b;
  *b = t;
}

快速排序的应用示例1

下面是一个使用快速排序算法解决整数数组去重的示例，即除去数组中的重复元素并排序：

#include <stdio.h>

void quicksort(int *arr, int left, int right);
void swap(int *a, int *b);

int main() {
  int arr[10] = {9, 8, 7, 6, 5, 4, 3, 2, 1, 7};
  quicksort(arr, 0, 9);
  int s = 0;
  for (int i = 1; i <= 9; i++) {
    if (arr[i] == arr[s]) {
      continue;
    }
    s++;
    arr[s] = arr[i];
  }
  for (int i = 0; i <= s; i++) {
    printf("%d ", arr[i]);
  }
  return 0;
}

void quicksort(int *arr, int left, int right) {
  if (left < right) {
    int pivot = arr[right];
    int i = left - 1;
    for (int j = left; j <= right - 1; j++) {
      if (arr[j] < pivot) {
        i++;
        swap(arr+i, arr+j);
      }
    }
    swap(arr+i+1, arr+right);
    int mid = i+1;
    quicksort(arr, left, mid-1);
    quicksort(arr, mid+1, right);
  }
}

void swap(int *a, int *b) {
  int t = *a;
  *a = *b;
  *b = t;
}

在上面的示例中，我们先对数组进行快速排序，然后再将重复元素去除并输出数组。这里的代码相当简单，就是记录一个索引，不断移动数组元素即可。

快速排序的应用示例2

下面是一个使用快速排序算法查找数组中第k小的数的示例：

#include <stdio.h>

void quicksort(int *arr, int left, int right);
int partition(int *arr, int left, int right);
void swap(int *a, int *b);

int main() {
  int arr[10] = {9, 8, 7, 6, 5, 4, 3, 2, 1, 0};
  quicksort(arr, 0, 9);
  int k = 4;
  printf("The %dth smallest element is %d.\n", k, arr[k-1]);
  return 0;
}

void quicksort(int *arr, int left, int right) {
  if (left < right) {
    int pivot_pos = partition(arr, left, right);
    quicksort(arr, left, pivot_pos-1);
    quicksort(arr, pivot_pos+1, right);
  }
}

int partition(int *arr, int left, int right) {
  int pivot = arr[right], i = left - 1;
  for (int j = left; j < right; j++) {
    if (arr[j] < pivot) {
      i++;
      swap(arr+i, arr+j);
    }
  }
  swap(arr+i+1, arr+right);
  return i+1;
}

void swap(int *a, int *b) {
  int t = *a;
  *a = *b;
  *b = t;
}

在上面的示例中，我们先对数组进行快速排序，然后再输出数组中第k小的元素，这需要我们稍微修改一下快速排序函数，以便在分割出pivot位置后直接返回该值即可。

总结

通过上面两个应用示例，我们可以看到，快速排序在实际中具有很高的效率和可用性，如果我们能够熟练掌握它，并在实践中合理地应用，将会大大提升我们的编程能力。