简析快速排序

 1 #include "stdlib.h"
 2 #include <stdio.h>
 3 
 4 //打印数组元素
 5 void printSelect(int arr[], int len){
 6     for (int i = 0; i<len; i++)
 7         printf("%d\t", arr[i]);
 8     printf("\n");
 9 }
10 
11 //快排
12 void quickSort(int arr[], int left, int right) {
13     int i = left, j = right;
14     int tmp = 0, key = 0;
15     if (left > right)
16         return;
17     key = arr[left]; //temp中存的就是基准数
18     while (i != j) { 
19         //先从右边开始找
20         while (arr[j] >= key && i < j) j--;
21         //再找右边的
22         while (arr[i] <= key && i < j) i++;
23         //交换两个数在数组中的位置
24         if (i < j){
25             tmp = arr[i];
26             arr[i] = arr[j];
27             arr[j] = tmp;
28         }
29     }
30     //最终将基准数归位
31     arr[left] = arr[i];
32     arr[i] = key;
33     //继续处理左边的，这里是一个递归的过程
34     quickSort(arr, left, i - 1);
35     //继续处理右边的 ，这里是一个递归的过程
36     quickSort(arr, i + 1, right);
37 }
38 
39 //c语言qsort比较函数
40 int qsortCompare(const void *a, const void *b){
41     return *(int *)a - *(int *)b;;
42 }
43 
44 int main() {
45     int arr[] = { 3, 5, 1, -7, 4, 9, -16, 8, 10, 4, -8 };
46     int arrLen = sizeof(arr) / sizeof(arr[0]);
47     //快速排序调用
48     quickSort(arr, 0, arrLen - 1);
49     //输出排序后的结果
50     printSelect(arr, arrLen);
51     
52     //库函数
53     int arrQSort[] = { 3, 5, 1, -7, 4, 9, -16, 8, 10, 4, -8 };
54     arrLen = sizeof(arrQSort) / sizeof(arrQSort[0]);
55     qsort(arrQSort, arrLen, sizeof(arrQSort[0]), qsortCompare);
56     printSelect(arrQSort, arrLen);
57 
58     system("pause");
59     return 0;
60 }

 1 #include "cstdlib"
 2 #include "iostream"
 3 #include <cstdio>
 4 
 5 using namespace std;
 6 //打印数组元素
 7 template<typename T> void printSelect(T arr[], int len){
 8     for (int i = 0; i<len; i++)
 9         cout << arr[i] << ‘ ‘;
10     cout << endl;
11 }
12 
13 //快排
14 template<typename T>void quickSort(T arr[], int left, int right) {
15     int i = left, j = right;
16     T tmp = 0, key = 0;
17     if (left > right)
18         return;
19     key = arr[left]; //temp中存的就是基准数
20     while (i != j) { 
21         //先从右边开始找
22         while (arr[j] >= key && i < j) j--;
23         //再找右边的
24         while (arr[i] <= key && i < j) i++;
25         //交换两个数在数组中的位置
26         if (i < j){
27             tmp = arr[i];
28             arr[i] = arr[j];
29             arr[j] = tmp;
30         }
31     }
32     //最终将基准数归位
33     arr[left] = arr[i];
34     arr[i] = key;
35     //继续处理左边的，这里是一个递归的过程
36     quickSort(arr, left, i - 1);
37     //继续处理右边的 ，这里是一个递归的过程
38     quickSort(arr, i + 1, right);
39 }
40 
41 
42 //借助c语言qsort
43 //c语言qsort比较函数
44 int qsortCompare(const void *a, const void *b){
45     return *(int *)a - *(int *)b;
46 }
47 
48 int main() {
49     double arr[] = { 3, 5, 1, -7, 4, 9.45, -16, 8, 10, 4, -8 };
50     int arrLen = sizeof(arr) / sizeof(arr[0]);
51     //快速排序调用
52     quickSort(arr, 0, arrLen - 1);
53     //输出排序后的结果
54     printSelect(arr, arrLen);
55 
56     //库函数
57     int arrQSort[] = { 3, 5, 1, -7, 4, 9, -16, 8, 10, 6, -8 };
58     arrLen = sizeof(arrQSort) / sizeof(arrQSort[0]);
59     qsort(arrQSort, arrLen, sizeof(arrQSort[0]), qsortCompare);
60     printSelect(arrQSort, arrLen);
61 
62     system("pause");
63     return 0;
64 }