快速排序,分别用C语言，C++,java,python编写出来

帆帆资源网

快速排序是一种交换类排序，可以理解成对冒泡排序的一种改进排序，但快速排序的复杂度相对于冒泡排序的提升相当大。

他的思路是，选取一个关键字K，将所有比K小的记录放在K前面，比K大的数放在K后面，一趟快速排序完成，完整的快速排序就是对分出的每个新数组再进行一次快速排序，也就是一趟排序的递归操作。

快速排序,分别用C语言，C++,java,python编写出来
下面是快速排序（Quick Sort）的不同语言实现示例：
1. C语言：

1. #include <stdio.h>
   
2. void swap(int* a, int* b) {
   
3.     int temp = *a;
   
4.     *a = *b;
   
5.     *b = temp;
   
6. }
   
7. int partition(int arr[], int low, int high) {
   
8.     int pivot = arr[high];
   
9.     int i = (low - 1);
   
10.      for (int j = low; j <= high - 1; j++) {
    
11.         if (arr[j] < pivot) {
    
12.             i++;
    
13.             swap(&arr[i], &arr[j]);
    
14.         }
    
15.     }
    
16.      swap(&arr[i + 1], &arr[high]);
    
17.     return (i + 1);
    
18. }
    
19. void quickSort(int arr[], int low, int high) {
    
20.     if (low < high) {
    
21.         int pi = partition(arr, low, high);
    
22.         quickSort(arr, low, pi - 1);
    
23.         quickSort(arr, pi + 1, high);
    
24.     }
    
25. }
    
26. 
    

复制代码

int main() {
    int arr[] = {64, 34, 25, 12, 22, 11, 90};
    int n = sizeof(arr) / sizeof(arr[0]);
     quickSort(arr, 0, n - 1);
     printf("Sorted array: \n");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr);
    }
    return 0;
}

2. C++:

1. #include <iostream>
   
2. using namespace std;
   
3. void swap(int& a, int& b) {
   
4.     int temp = a;
   
5.     a = b;
   
6.     b = temp;
   
7. }
   
8. int partition(int arr[], int low, int high) {
   
9.     int pivot = arr[high];
   
10.     int i = (low - 1);
    
11.      for (int j = low; j <= high - 1; j++) {
    
12.         if (arr[j] < pivot) {
    
13.             i++;
    
14.             swap(arr[i], arr[j]);
    
15.         }
    
16.     }
    
17.      swap(arr[i + 1], arr[high]);
    
18.     return (i + 1);
    
19. }
    
20. void quickSort(int arr[], int low, int high) {
    
21.     if (low < high) {
    
22.         int pi = partition(arr, low, high);
    
23.         quickSort(arr, low, pi - 1);
    
24.         quickSort(arr, pi + 1, high);
    
25.     }
    
26. }
    
27. 
    

复制代码

int main() {
    int arr[] = {64, 34, 25, 12, 22, 11, 90};
    int n = sizeof(arr) / sizeof(arr[0]);
     quickSort(arr, 0, n - 1);
     cout << "Sorted array: \n";
    for (int i = 0; i < n; i++) {
        cout << arr << " ";
    }
    return 0;
}



3. Java:

1. import java.util.Arrays;
   
2. class QuickSort {
   
3.     public static void swap(int[] arr, int i, int j) {
   
4.         int temp = arr[i];
   
5.         arr[i] = arr[j];
   
6.         arr[j] = temp;
   
7.     }
   
8.      public static int partition(int[] arr, int low, int high) {
   
9.         int pivot = arr[high];
   
10.         int i = (low - 1);
    
11.          for (int j = low; j <= high - 1; j++) {
    
12.             if (arr[j] < pivot) {
    
13.                 i++;
    
14.                 swap(arr, i, j);
    
15.             }
    
16.         }
    
17.          swap(arr, i + 1, high);
    
18.         return (i + 1);
    
19.     }
    
20.      public static void quickSort(int[] arr, int low, int high) {
    
21.         if (low < high) {
    
22.             int pi = partition(arr, low, high);
    
23.             quickSort(arr, low, pi - 1);
    
24.             quickSort(arr, pi + 1, high);
    
25.         }
    
26.     }
    
27.    
    
28. }

复制代码

public static void main(String[] args) {
        int[] arr = {64, 34, 25, 12, 22, 11, 90};
        int n = arr.length;
         quickSort(arr, 0, n - 1);
         System.out.println("Sorted array: ");
        for (int i = 0; i < n; i++) {
            System.out.print(arr + " ");
        }
    }



4. Python:

1. def partition(arr, low, high):
   
2.     pivot = arr[high]
   
3.     i = low - 1
   
4.      for j in range(low, high):
   
5.         if arr[j] < pivot:
   
6.             i += 1
   
7.             arr[i], arr[j] = arr[j], arr[i]
   
8.      arr[i + 1], arr[high] = arr[high], arr[i + 1]
   
9.     return i + 1
   
10. def quickSort(arr, low, high):
    
11.     if low < high:
    
12.         pi = partition(arr, low, high)
    
13.         quickSort(arr, low, pi - 1)
    
14.         quickSort(arr, pi + 1, high)
    
15. 
    

复制代码

arr = [64, 34, 25, 12, 22, 11, 90]
n = len(arr)
quickSort(arr, 0, n - 1)
print("Sorted array:")
for i in range(n):
    print(arr, end=" ")