用c实现的各种排序的方法

#include <stdio.h> void swap(int *a, int *b); void bubble_sort(int a[], int n); void select_sort(int a[], int n); void insert_sort(int a[], int n); void shell_sort(int a[], int n); void heap_adjust(int a[], int i, int n); void heap_sort(int a[], int n); void quick_sort(int a[], int low, int high); int main() { // int arr[] = {0,2,3,1,6,9,8,7,4,5}; int arr[1000]; int n,m; printf("请输入你排序的数字个数：\n"); scanf("%d",&n); printf("请输入你排序的%d个数字:\n",n); for(int i=0;i<n;i++) scanf("%d",&arr[i]); printf("请输入你所使用的排序方法(数字)：\n1 冒泡排序\n2 选择排序\n3 插入排序\n4 希尔排序\n5 堆排序\n6 快速排序\n"); scanf("%d",&m); switch(m){ case 1: bubble_sort(arr, n); break; case 2: select_sort(arr, n); break; case 3: insert_sort(arr, n); break; case 4: shell_sort(arr, n); break; case 5: heap_sort(arr, n); break; case 6: quick_sort(arr, 0, n-1); break; } for (int i = 0; i < n; i++) { printf("%d\n", arr[i]); } return 0; } //交換數據 void swap(int *a, int *b) { int tmp = *a; *a = *b; *b = tmp; } //冒泡排序法 //時間複雜度O(n^2) 空間複雜度O(1) void bubble_sort(int a[], int n) { int i, j; //旗幟位，判斷這次遍歷是否有交換 int flag = 1; for (i = 0; i < n && flag; i++) { flag = 0; for (j = n-2 ; j >= i; j--) { if (a[j] > a[j+1]) { swap(&a[j], &a[j+1]); flag = 1; } } } } //簡單選擇排序 //時間複雜度O(n^2) 空間複雜度O(1) void select_sort(int a[], int n) { int i, j, min; for (i = 0; i < n ; i++) { min = i; for (j = i+1; j < n; j++) { if (a[j] < a[min]) { min = j; } } if (min != i) { swap(&a[min], &a[i]); } } } //直接插入排序 //時間複雜度O(n^2) 空間複雜度O(1) void insert_sort(int a[], int n) { for (int i = 0; i < n ; i++) { int temp = a[i]; int j = i-1; while (j>=0 && a[j] > temp) { a[j+1] = a[j]; j--; } a[j+1] = temp; } } //希爾排序 //時間複雜度為O(nlogn) 空間複雜度為O(1) void shell_sort(int a[], int n) { int i,j,temp; int gap = 0; while (gap <= n) gap = gap*3+1; while (gap > 0) { for (i = gap; i < n; i++) { temp = a[i]; j = i - gap; while (j >= 0 && a[j] > temp) { a[j+gap] = a[j]; j = j - gap; } a[j+gap] = temp; } gap = (gap-1)/3; } } //堆排序 //時間複雜度為O(nlogn) 空間複雜度為O(1) void heap_sort(int a[], int n) { for (int i = n/2 - 1; i >= 0; i--) { heap_adjust(a, i, n); } for (int i = n-1; i > 0; i--) { swap(&a[0], &a[i]); heap_adjust(a, 0, i); } } //構建大頂堆 void heap_adjust(int a[], int i, int n) { int child, temp; for (temp = a[i]; 2*i+1 < n; i = child) { child = 2*i+1; //取得較大子結點索引 if (child < n -1 && a[child] < a[child+1]) child++; //保證父結點大於等於子結點 if (temp < a[child]) swap(&a[i], &a[child]); else break; } } //快速排序 //時間複雜度為O(nlogn) 空間複雜度為O(logn) ~ O(n) void quick_sort(int a[], int low, int high) { int i = low+1; int j = high; int key = a[low]; if (low >= high) return; while (1) { while (key<a[j]) j--; while (key>a[i] && i<j) i++; if (i >= j) break; swap(&a[i], &a[j]); if (a[i] == key) j--; else i++; } swap(&a[low], &a[j]); if (i-1>low) quick_sort(a, low, i-1); if (j+1<high) quick_sort(a, j+1, high); }