# 快速排序算法(Quicksort)

jopen 4年前

{ 4, 1, 2, 3, 0 }, { 5 }, { 7 }, { 8 }, { 9 }

C实现代码如下

`#include <stdio.h>    #define LEN 10    int partition(int *arr, int start, int end)  {      int pivot = arr[end];      int i = start;      int j;      int tmp;      for (j = start; j < end; ++j) {          if (arr[j] <= pivot) {              tmp = arr[i];              arr[i] = arr[j];              arr[j] = tmp;              ++i;          }      }      arr[end] = arr[i];      arr[i] = pivot;      return i;  }    int quicksort(int *arr, int start, int end)  {      int pivot_location;      if (start < end) {          pivot_location = partition(arr, start, end);          quicksort(arr, start, pivot_location - 1);          quicksort(arr, pivot_location + 1, end);      }  }    int main()  {      int i;      int arr[LEN] = { 4, 8, 1, 2, 9, 7, 3, 0, 5, 6 };      quicksort(arr, 0, LEN - 1);      for (i = 0; i < LEN; ++i)          printf("%d\n", arr[i]);      return 0;  }`

Java实现代码如下

`public class QuickSort {        // Sort a list of numbers in an array within [start, end]      public void quickSort(int[] A, int start, int end) {          if (start < end) {              int pivotLocation = partition(A, start, end);              quickSort(A, start, pivotLocation - 1);              quickSort(A, pivotLocation + 1, end);          }      }            // Select A[end] as the pivot, separate the array into two parts.      private int partition(int[] A, int start, int end) {          int pivot = A[end];          int i = start;          for (int j = start; j < end; ++j) {              if (A[j] <= pivot) {                  int tmp = A[i];                  A[i] = A[j];                  A[j] = tmp;                  ++i;              }          }                    A[end] = A[i];          A[i] = pivot;          return i;      }            public static void main(String[] args) {          QuickSort q = new QuickSort();          int[] A = { 4, 8, 1, 2, 9, 7, 3, 0, 5, 6 };          q.quickSort(A, 0, A.length - 1);          for (int i = 0; i < A.length; ++i) {              System.out.println(A[i]);          }      }    }`