常见排序算法代码(冒泡排序、选择排序、插入排序、希尔排序、快速排序、归并排序、堆排序、基数排序)
- 格式：doc
- 大小：40.00 KB
- 文档页数：6
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 (array[j] > array[ j + 1])
{
flag = true;
int temp = array[j];
array[j] = array[j + 1];
array[j + 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 (array[j] < array[k])
{
k = j;
}
}
if (k != i)
{
int temp = array[k];
array[k] = array[i];
array[i] = temp;
}
}
}
void InsertSort(int array[], int n)
{
int i, j, temp;
for (i = 1; i < n; i++)
{
temp = array[i];
j = i - 1;
while (j >= 0 && array[j] > temp)
{
array[j + 1] = array[j];
j--;
}
array[j + 1] = temp;
}
}
// 快速排序
void QSort(int array[], int l, int r) {
int i = l, j = r;
int temp = array[l];
while (i < j)
{
while (i < j && temp < array[j])
{
j--;
}
if (i < j)
{
array[i] = array[j];
i++;
}
while (i < j && temp > array[i])
{
i++;
}
if (i < j)
{
array[j] = array[i];
j--;
}
array[i] = 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 = array[i];
j = i - d;
while (j >= 0 && array[j] > temp)
{
array[j + d] = array[j];
j -= d;
}
array[j + d] = temp;
}
}
}
// 堆排序
void AdjustHeap(int array[], int i, int n) {
int j = 2 * i, temp;
while (j <= n)
{
if (j < n && array[j - 1] < array[j])
{
j += 1;
}
if (array[i - 1] < array[j - 1])
{
temp = array[i - 1];
array[i - 1] = array[j - 1];
array[j - 1] = temp;
i = j;
j = 2 * i;
}
else
{
break;
}
}
}
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 = array[0];
array[0] = array[i - 1];
array[i - 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 int[n1 + 1];
R = new int[n2 + 1];
for (i = 0; i < n1; i++)
L[i] = array[p + i];
for (i = 0; i < n2; i++)
R[i] = array[q + 1 + i];
L[n1] = INT_MAX;
R[n2] = INT_MAX;
for (i = 0, j = 0, k = p; k <= r; k++)
{
if (L[i] <= R[j])
{
array[k] = L[i++];
}
else
{
array[k] = R[j++];
}
}
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);
}
else
{
return;
}
}
// 基数排序
#define NUM 10
void 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++)
{
ppArr[i] = new int[n];
}
int pNum[NUM];
// 分趟分配收集
while (d < D)
{
for (i = 0; i < NUM; i++)
{
pNum[i] = -1;
}
for (i = 0; i < n; i++)
{
j = (Array[i] / l) % NUM;
k = ++pNum[j];
ppArr[j][k] = Array[i];
}
for (k = 0, i = 0; i < NUM; i++)
{
for (j = 0; j <= pNum[i]; j++)
{
Array[k++] = ppArr[i][j];
}
}
d++;
l *= 10;
}
}。
