还是看代码吧:
/*************************************************************************
> File Name: sort.c
> Author: Netcan
> Mail: 1469709759@qq.com
> Created Time: 2014/12/15 22:14:52
************************************************************************/
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#include<string.h>
#define LEN 25
// 以下几大排序算法是升序排序
void Show_Num(int *n); // 显示数组的值
void Bubble_Sort(int *n); // 冒泡排序
void Selection_Sort(int *n); // 选择排序
void Shell_Insert_Sort(int *n, int dk); // 希尔插入排序
void Shell_Sort(int *n); // 希尔排序
void Quick_Sort(int *n, int first, int last); // 快速排序
void Merge_Array(int *n,int *tmp,int first,int mid,int last); // 归并数组
void Merge_Sort(int *n,int *tmp,int first,int last); // 归并排序
int main() {
static int num[LEN]; // 存放 LEN 个随机数
static int sort_num[LEN]; // 排序后的数组
static int merge_tmp[LEN]; // 归并用的数组
srand((int)time(0));
for(int i=0; i<LEN; ++i)
num[i]=rand()%100+1; // 产生 1-100 的随机数
puts("Orignal Array:");
Show_Num(num); // 输出随机值
memcpy(sort_num, num, LEN*sizeof(int));
puts("Bubble_Sort:");
Bubble_Sort(sort_num); // 冒泡
Show_Num(sort_num);
memcpy(sort_num, num, LEN*sizeof(int));
puts("Selection_Sort:");
Selection_Sort(sort_num); // 选择排序
Show_Num(sort_num);
memcpy(sort_num, num, LEN*sizeof(int));
puts("Insert_Sort:");
Shell_Insert_Sort(sort_num,1); // 插入排序,dk == 1
Show_Num(sort_num);
memcpy(sort_num, num, LEN*sizeof(int));
puts("Shell_Sort:");
Shell_Sort(sort_num); // 希尔排序
Show_Num(sort_num);
memcpy(sort_num, num, LEN*sizeof(int));
puts("Quick_Sort:");
Quick_Sort(sort_num, 0, LEN-1); // 快速排序
Show_Num(sort_num);
memcpy(sort_num, num, LEN*sizeof(int));
puts("Merge_Sort:");
Merge_Sort(sort_num, merge_tmp, 0, LEN-1); // 归并排序
Show_Num(sort_num);
return 0;
}
void Show_Num(int *n)
{
for(int i=0; i<LEN; ++i)
printf("%4d",n[i]);
puts("");
return;
}
void Bubble_Sort(int *n)
{
/* 冒泡排序
* 将每个数与其后的数一一比较,
* 发现比其小的就交换两数的位置
* 直到该数组遍历完成
*/
for(int i=0;i<LEN;++i)
for(int j=i+1;j<LEN;++j)
if(n[i]>n[j]) { // 交换数字
int t=n[i];
n[i]=n[j];
n[j]=t;
}
return;
}
void Selection_Sort(int *n)
{
/* 从第一个数开始,遍历其后的数,选出最小的数与第一个数交换
* 到第二个数,遍历其后的数,选出次最小的数与第二个数交换
* 一次类推
* 直到整个数组遍历完
*/
for(int i=0;i<LEN;++i) {
int mini = i;
for(int j=i+1;j<LEN;++j)
if(n[mini] > n[j] )
mini = j;
int t=n[mini];
n[mini] = n[i];
n[i] = t;
}
return;
}
void Shell_Insert_Sort(int *n, int dk)
{
/* 希尔插入排序,若 dk == 1 则为插入排序,dk 为步长
* 从首个元素 (第 dk 个) 开始以步长为 dk 遍历
* 若当前元素比其前 dk 个元素小则开始插入
* 将数字往右挪,直到空出合适的位置给其插入
*/
for(int i=dk;i<LEN;++i) {
if(n[i]<n[i-dk]) { // 如果该元素比前一个小的话就需要插入
int t=n[i]; // 监视哨 t 用于保存待插入的元素
int j=i-dk;
for(; j >= 0 && t < n[j]; j-=dk) // 开始将数值往右挪,直到空出待插入的位置
n[j+dk]=n[j];
n[j+dk]=t; // 插入元素
}
}
return;
}
void Shell_Sort(int *n)
{
/* 希尔排序
* 每次取 dk 等于待排序长度的一半,
* 执行希尔插入排序
* 直到 dk < 1 (dk == 0)为止
*/
int dk=LEN/2;
while(dk >= 1) {
Shell_Insert_Sort(n, dk);
dk/=2;
}
}
void Quick_Sort(int *n, int first, int last)
{
/* 快速排序
* 1. 从首个元素开始进行调整(见代码),将其放到合适的位置,
* 2. 使该数左边的数全部比该数小(等于),该数右边的数全部比该数大(等于)
* 3. 以该数为分割点,将该数组分割为左右两个数组
* 4. 将左右两个数组分别执行 1 到 3 步,直到全部有序为止
*/
if(first > last)
return;
int low = first;
int high = last;
int t = n[low];
while(low < high) {
while(low < high && n[high] >= t)
high--;
n[low] = n[high];
while(low < high && n[low] <= t )
low++;
n[high] = n[low];
}
n[low] = t;
Quick_Sort(n, 0, low-1);
Quick_Sort(n, low+1, last);
}
void Merge_Array(int *n,int *tmp,int first,int mid,int last)
{
/* 归并数组
* 将两个有序数组合成为一个有序数组
*
*/
int i = first, j = mid+1, k=0;
while(i <= mid && j <= last)
if(n[i] <= n[j])
tmp[k++] = n[i++];
else
tmp[k++] = n[j++];
while(i <= mid)
tmp[k++] = n[i++];
while(j <= last)
tmp[k++] = n[j++];
memcpy(n+first,tmp,(k)*sizeof(int)); // 将归并后的数组拷贝到 n 中
}
void Merge_Sort(int *n,int *tmp,int first,int last)
{
/* 归并排序
* 将数组分割成以一个元素为数组,并依次归并这些数组
* 然后分割成以两个元素为一个数组,并两两数组归并
* 然后 4 个一组,以此类推
*/
if(first < last)
{
int mid = (first + last)/2; //
Merge_Sort(n,tmp,first,mid);
Merge_Sort(n,tmp,mid+1,last);
Merge_Array(n,tmp,first,mid,last);
}
}