本文共 3832 字，大约阅读时间需要 12 分钟。
总结并编写了部分常用的排序算法，包括前向、后向冒泡排序、简单选择排序、直接插入排序、希尔排序、堆排序、并归排序和快速排序。
具体的原理请参考《大话数据结构》。#include#include //从前向后冒泡 =======================================================void bubble(int arr[], int n){ for (int i = 0; i < n - 1; i++) { for (int j = 0; j < n - 1 - i; j++) { if (arr[j] > arr[j + 1]) { int temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; } } }}//从后向前冒泡void bubble2(int arr[], int n){ for (int i = 0; i < n - 1; i++) { for (int j = n - 1; j > i; j--) { if (arr[j - 1] > arr[j]) { int temp = arr[j]; arr[j] = arr[j - 1]; arr[j - 1] = temp; } } }}//选择排序 =======================================================void selectsort(int arr[], int n){ for (int i = 0; i < n ; i++) { int index = i; for (int j = i + 1; j < n; j++) { if (arr[index] > arr[j]) index = j; } if (i != index) { int temp = arr[i]; arr[i] = arr[index]; arr[index] = temp; } }}//插入排序 =======================================================void insertionsort(int arr[], int n){ for (int i = 1; i < n; i++) { int temp = arr[i]; while (i >= 0 && arr[i - 1] > temp) { arr[i] = arr[i - 1]; i--; } arr[i] = temp; }}//希尔排序 =======================================================void shellsort(int arr[], int n){ int gap = n; int temp; int i, j; do { gap = gap / 2; for (i = gap; i < n; i++) { if (arr[i] < arr[i - gap]) { temp = arr[i]; for (j = i - gap; j >= 0 && temp < arr[j]; j -= gap) arr[j + gap] = arr[j]; arr[j + gap] = temp; } } } while (gap > 1);}//堆排序 =======================================================void heapadjust(int arr[], int s, int m){ int j; int temp = arr[s]; for (j = (2*s)+1; j < m; j *= 2) { if (j < m && arr[j] < arr[j + 1]) j++; if (temp > arr[j]) break; arr[s] = arr[j]; s = j; } arr[s] = temp;}void heapsort(int arr[], int n){ int i; for (i = (n/2)-1; i >= 0; i--) heapadjust(arr, i, n); for (i = 0; i < n; i++) { int temp = arr[0]; arr[0] = arr[n-1-i]; arr[n-1-i] = temp; heapadjust(arr, 0, n-1-i-1); }}//归并排序void merge(int arr[], int start, int mid, int end) { int* result = (int*)malloc((end + 1) * sizeof(int)); int k = 0; int i = start; int j = mid + 1; while (i <= mid && j <= end) { if (arr[i] < arr[j]) { result[k++] = arr[i++]; } else { result[k++] = arr[j++]; } } if (i == mid + 1) { while (j <= end) result[k++] = arr[j++]; } if (j == end + 1) { while (i <= mid) result[k++] = arr[i++]; } for (j = 0, i = start; j < k; i++, j++) { arr[i] = result[j]; } free(result);}void mergeSort(int arr[], int start, int end){ if (start >= end) return; int mid = (start + end) / 2; mergeSort(arr, start, mid); mergeSort(arr, mid + 1, end); merge(arr, start, mid, end);}//快速排序 =======================================================int fun(int arr[], int low, int high){ int key; key = arr[low]; while (low < high) { while (low < high && arr[high] >= key) high--; if (low < high) arr[low++] = arr[high]; while (low < high && arr[low] <= key) low++; if (low < high) arr[high--] = arr[low]; } arr[low] = key; return low;}void quicksort(int arr[], int start, int end){ int pos; if (start < end) { pos = fun(arr, start, end); quicksort(arr, start, pos - 1); quicksort(arr, pos + 1, end); }}//=======================================================//=======================================================int main(){ int arr[] = { 9,5,1,4,0,7,2,6,8,3 }; //冒泡排序 //bubble(arr, 10); //bubble2(arr, 10); //选择排序 //selectsort(arr, 10); //插入排序 //insertionsort(arr, 10); //希尔排序 //shellsort(arr, 10); //堆排序 //heapsort(arr, 10); //归并排序 //mergeSort(arr, 0, 9); //快速排序 quicksort(arr, 0, 9); for (int i = 0; i < 10; i++) printf("%d ", arr[i]); return 0;}
转载地址：http://hhmji.baihongyu.com/