六大排序算法的实现
程序员文章站
2024-03-16 12:20:40
...
大家都知道有八大排序算法
先从6个最简单的开始
冒泡排序,快速选择排序,直接选择排序,归并排序,快速选择排序,希尔排序。
以下代码:
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#define SEP "****************************************************"
static int cnt = 1;
void Print(int*a, int len) {
printf("第%d次排序为:", cnt++);
for (int i = 0; i < len; i++) {
if (i == len - 1) printf("%d\n", a[i]);
else
printf("%d ", a[i]);
}
}
void swap(int*a, int*b) {
int temp = *a;
*a = *b;
*b = temp;
}
//冒泡排序
void Bumble(int*a, int len) {
int i, j;
for (i = 1; i < len; i++) {
for (j = 0; j < len - i; j++) {
//两两比较,最大的值向后冒,然后忽略其索引
if (a[j] > a[j + 1]) {
swap(a + j, a + j + 1);
}
}
Print(a, len);
}
}
//直接选择排序
void Select(int*a, int len) {
int i, j;
for (i = 0; i < len; i++) {
//与初始元素作比较,把最小的元素放到此索引上,然后忽略此索引继续
for (j = i; j < len; j++) {
if (a[i] > a[j]) {
swap(&a[i], &a[j]);
}
}
Print(a, len);
}
}
//直接插入排序
void Insert(int*a, int len) {
for (int i = 1; i < len; i++) {
//从第二个元素开始向前比较,遇到比它大的则向前移动,直到遇见比它小的,插入,然后以此轮推
int j = i;
int x = a[i];//要把a[i]的值暂时赋给x,之后的移位赋值会把a[i]的值改变
while (x < a[j - 1] && j>0) {
a[j] = a[j - 1];//向后移一位
j--;
}
a[j] = x;//这个过程就把a[i]按顺序插到依次比a[i]大的值前面啦
Print(a, len);
}
}
//快速排序
void Quicksort(int*a, int lowt, int hight, int len) {
int low = lowt, high = hight;
int Index = a[low];
int IsSwap = 0;//用来判断这一轮是否进行了排序交换
while (low < high) {
IsSwap = 1;
while (low < high&&Index <= a[high]) high--;
//注:一定要让Index<=边缘值,相等的情况下没必要置换
//若有两个相等的值,在快排一侧的最后会造成无限循环
//swap(&Index, a + high);
//不能指针交换&Index的值,交换后Index的值会发生改变
swap(a + low, a + high);
while (low < high&&Index >= a[low]) low++;
swap(a+high, a + low);
}
if (IsSwap) Print(a, len);//如果这一轮进行了交换,则打印
if (lowt <hight) {
//对递归函数设置一个判定点
Quicksort(a, low + 1, hight, len);
Quicksort(a, lowt, low - 1, len);
}
}
//归并排序
void Merge(int *a, int *b, int low, int med, int high) {
int i = low, j = med + 1, k = low;
while (k <= med&&j <= high) {
//把数组分为两部分,分别比较大小,把较小的值放在数组b里
if (a[k] < a[j]) b[i++] = a[k++];
else b[i++] = a[j++];
}
//再把比较所剩余的数组加上
while (k <= med) b[i++] = a[k++];
while (j <= high) b[i++] = a[j++];
}
void MergeSort(int*a, int*b, int length) {
int len = 1, i, med;
int*temp;
while (len < length) {
//设置循环条件,只要中间点在length之内,就能进行归并排序
med = len;
i = 0;
len *= 2;//执行归并排序的两个数组变量的长度
while (i + len < length) {
Merge(a, b, i, i + med - 1, i + len - 1);
i += len;
}
if (i + med < length) {
Merge(a, b, i, i + med - 1, length - 1);
}
else {
Merge(a, b, i, i, length - 1);
}
Print(b, length);
temp = a;
a = b;
b = temp;//最后一定要把数组的地址交换过来,便于对结果进行下一次归并
}
}
//希尔排序
void Shellsort(int*a, int len, int split) {
split /= 2;//split为选取的一个增量因子
while (split >= 1) {
//等于1时就相当于最后的直接插入排序
for (int i = split; i < len; i++) {
int j = i;
int x = a[i];
while (j&&x<a[j - split]) {
a[j] = a[j - split];
j -= split;
}
a[j] = x;
}
split /= 2;
Print(a, len);
}
}
void init(int*a, int*b, int len) {
for (int i = 0; i < len; i++) {
a[i] = b[i];
}
}
int main() {
clock_t start, end;//用于显示程序所运行的时间
start = clock();//开始计时
int a[] = { 5,2,3,6,3,66,22,34,26,43 }, time;
int i, j;
/*
static const int len = sizeof(a) / sizeof(int);
//设为静态常量,可以当做一个常数来定义数组了(Ps:这功能在visual studio声明数组中可用)
*/
//int len = 11; //动态变量(Ps:这功能在code blocks中声明数组可用),二者在此的声明方式交换则报错
//而且此声明必须是在.cpp文件里方可行,故声明函数时最好用常数或宏定义来声明
//int b[len], c[len] = { 0 };
const int len = 10; //const len=11(code blocks可默认为const int,但visual studio则报错)
int b[50], c[50] = { 0 };
for (i = 0; i < len; i++)
b[i] = a[i];
init(a, b, len);//初始化数组a
cnt = 1;
Bumble(a, len);
printf("冒泡排序\n%s\n", SEP);
init(a, b, len);
cnt = 1;
Insert(a, len);
printf("直接插入排序\n%s\n", SEP);
init(a, b, len);
cnt = 1;
Select(a, len);
printf("直接选择排序\n%s\n", SEP);
init(a, b, len);
cnt = 1;
Quicksort(a, 0, len - 1, len);
printf("快速选择排序\n%s\n", SEP);
init(a, b, len);
cnt = 1;
Shellsort(a, len, len);
printf("希尔排序\n%s\n", SEP);
init(a, b, len);
cnt = 1;
MergeSort(a, c, len);
printf("归并排序\n%s\n", SEP);
end = clock();
time = end - start;
printf("程序用时0.%03ds", time);
return 0;
}
为了比较直观的表示,定义了init()函数使数组a初始化,并打印出了每个排序的步骤.