常见排序算法代码(冒泡排序、选择排序、插入排序、希尔排序、快速排序、归并排序、堆排序、基数排序).doc
Four short words sum up what has lifted most successful individuals above the crowd: a little bit more.-author-date常见排序算法代码(冒泡排序、选择排序、插入排序、希尔排序、快速排序、归并排序、堆排序、基数排序)常见排序算法代码(冒泡排序、选择排序、插入排序、希尔排序、快速排序、归并排序、堆排序、基数排序)/ 冒泡排序void BuddleSort(int array, int n)int i, j;bool flag = true;for (i = 1; flag && i < n; i+)flag = false;for (j = 0; j < n - i; j+)if (arrayj > array j + 1)flag = true;int temp = arrayj;arrayj = arrayj + 1;arrayj + 1 = temp;/ 选择法void SelectSort(int array, int n)int i, j, k;for (i = 0; i < n; i+)k = i;for (j = i + 1; j < n; j+)if (arrayj < arrayk)k = j;if (k != i)int temp = arrayk;arrayk = arrayi;arrayi = temp;/ 插入排序void InsertSort(int array, int n)int i, j, temp;for (i = 1; i < n; i+)temp = arrayi;j = i - 1;while (j >= 0 && arrayj > temp)arrayj + 1 = arrayj;j-;arrayj + 1 = temp;/ 快速排序void QSort(int array, int l, int r)int i = l, j = r;int temp = arrayl;while (i < j)while (i < j && temp < arrayj)j-;if (i < j)arrayi = arrayj; i+;while (i < j && temp > arrayi)i+;if (i < j)arrayj = arrayi;j-;arrayi = temp;if (l < i)QSort(array, l, i - 1);if (j < r)QSort(array, j + 1, r);/ 希尔排序void ShellSort(int array, int n)int i, j, d = n;while (d != 1)d = (d + 1) / 2;for (i = d; i < n; i+)int temp = arrayi;j = i - d;while (j >= 0 && arrayj > temp)arrayj + d = arrayj;j -= d;arrayj + d = temp;/ 堆排序void AdjustHeap(int array, int i, int n)int j = 2 * i, temp;while (j <= n)if (j < n && arrayj - 1 < arrayj)j += 1;if (arrayi - 1 < arrayj - 1)temp = arrayi - 1;arrayi - 1 = arrayj - 1;arrayj - 1 = temp;i = j;j = 2 * i;elsebreak;void HeapSort(int array, int n)int i, temp;/ 将初始无序数转为小根堆for (i = n / 2; i > 0; i-) AdjustHeap(array, i, n); / 进行n - 1趟排序for (i = n; i > 1; i-)temp = array0;array0 = arrayi - 1;arrayi - 1 = temp;AdjustHeap(array, 1, i - 1);/ 归并排序#include <limits.h>void Merge(int array, int p, int q, int r)int n1 = q - p + 1;int n2 = r - q;int *L, *R, i, j, k;L = new intn1 + 1;R = new intn2 + 1;for (i = 0; i < n1; i+)Li = arrayp + i;for (i = 0; i < n2; i+)Ri = arrayq + 1 + i;Ln1 = INT_MAX;Rn2 = INT_MAX;for (i = 0, j = 0, k = p; k <= r; k+)if (Li <= Rj)arrayk = Li+;elsearrayk = Rj+;delete L;delete R;void MergeSort(int array, int p, int r)if (p < r)int q = (p + r) / 2;MergeSort(array, p, q);MergeSort(array, q + 1, r);Merge(array, p, q, r);elsereturn;/ 基数排序#define NUM 10void RadixSort(int Array, int n, int D)int i, j, k, l = 1, d = 0;/ 分配中间存储空间int *ppArr = new int*NUM;for (i = 0; i < NUM; i+)ppArri = new intn;int pNumNUM;/ 分趟分配收集while (d < D)for (i = 0; i < NUM; i+)pNumi = -1;for (i = 0; i < n; i+)j = (Arrayi / l) % NUM;k = +pNumj;ppArrjk = Arrayi;for (k = 0, i = 0; i < NUM; i+)for (j = 0; j <= pNumi; j+)Arrayk+ = ppArrij;d+;l *= 10;-
