排序算法总结(C语言版)
1. 插入排序
1.1 直接插入排序
1.2 Shell排序
2. 交换排序
2.1 冒泡排序
2.2 快速排序
3. 选择排序
1.插入排序
1.1 直接插入排序
将已排好序的部分num[0]~num[i]后的一个元素num[i+1]插入到之前已排好序的部分中去。
代码:
/*
* 直接插入排序,由小到大
*/
# define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
# define NUM 10 void InsertSort(int num[],int n)
{
int i, j;
int temp; for (i = 1; i < n; i++)
{
temp = num[i];
for (j = i - 1; j >= 0 && num[j] > temp; j--)
{
num[j + 1] = num[j];
}
num[j + 1] = temp;
}
}
void main()
{
int num[NUM];
int i; for (i = 0; i < NUM; i++)
scanf("%d", num + i); InsertSort(num, NUM); for (i = 0; i < NUM; i++)
printf("%-3d", num[i]);
}
1.2 Shell排序
先将整个待排记录序列分隔成若干个子序列分别进行直接插入排序,待整个序列中的记录“基本有序”时,再对全体记录进行一次直接插入排序。
子序列选择:将相隔某个增量的记录组成一个序列。
“增量序列”选择注意事项:应使增量序列中的值没有除1之外的公因子,并且最后一个增量值必须为1。
代码:
/*
* 希尔排序,由小到大
*/
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#define NUM 10 void ShellSort(int num[], int n)
{
int i, j, k;
int temp;
int inc; //增量序列为{5,2,1}
for (inc = 5; inc >= 1; inc /= 2)
{
//如果增量为inc,则需要分成inc组进行直接插入排序
for (k = 0; k < inc; k++)
{
for (i = k + inc; i < n; i += inc)
{
temp = num[i];
for (j = i - inc; j >= 0 && num[j] > temp; j -= inc)
{
num[j + inc] = num[j];
}
num[j + inc] = temp;
}
}
}
} void main()
{
int num[NUM];
int i; for (i = 0; i < NUM; i++)
scanf("%d", num + i); ShellSort(num, NUM); for (i = 0; i < NUM; i++)
printf("%-3d ", num[i]);
}
2.交换排序
2.1 冒泡排序
代码:
/*
* 冒泡排序,由小到大
*/
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#define NUM 10 void BubbleSort(int num[], int n)
{
int i, j;
int temp; for (i = 0; i < n - 1; i++)
{
for (j = 0; j < n - i - 1; j++)
{
if (num[j] > num[j + 1])
{
temp = num[j];
num[j] = num[j + 1];
num[j + 1] = temp;
}
}
}
}
void main()
{
int num[NUM];
int i; for (i = 0; i < NUM; i++)
scanf("%d", num + i); BubbleSort(num, NUM); for (i = 0; i < NUM; i++)
printf("%-3d ", num[i]);
}
2.2 快速排序
快速排序(Quick Sort)是对冒泡排序的一种改进。基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以达到整个序列有序。
设要排序的数组是A[0],……,A[N-1],首先任意选取一个数据(通常选用数组的第一个数)作为枢轴,然后将所有比它小的数都放到它前面,所有比它大的数都放到它后面,这个过程称为一趟快速排序。
代码1:
/*
* 快速排序,由小到大。
* 利用快速排序的基本思想:枢轴左边的所有元素均不大于枢轴右边的所有元素。
* 常规的做法是同时从后往前和从前往后遍历,直至head和tail指向同一个元素。
* 此处的做法是只从前往后遍历,将比枢轴元素小的元素移动到枢轴之前。
*/
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#define NUM 10 void QuickSort(int num[], int head, int tail)
{
int temp;
int pivot = head;
int i,j; //一次划分,从head+1开始,将比枢轴元素小的元素移动到枢轴之前。
for (i = head + 1; i <= tail; i++)
{
if (num[i] < num[pivot])
{
temp = num[i];
for (j = i - 1; j >= pivot; j--)
{
num[j + 1] = num[j];
}
num[pivot++] = temp;
}
} //一次划分之后,将分成的两个序列分别进行快速排序。
if (head != pivot && head != pivot - 1)
{
QuickSort(num, head, pivot - 1);
}
if (pivot != tail && pivot + 1 != tail)
{
QuickSort(num, pivot + 1, tail);
}
} void sort(int num[], int n)
{
QuickSort(num, 0, n - 1);
} void main()
{
int num[NUM];
int i; for (i = 0; i < NUM; i++)
scanf("%d", num + i); sort(num, NUM); for (i = 0; i < NUM; i++)
printf("%-3d ", num[i]);
}
代码2:
/*
* 快速排序,由小到大。
* 常规的做法:同时从后往前和从前往后遍历,直至head和tail指向同一个元素。
*/
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#define NUM 10 /*
* 一次划分函数。
* 函数功能:将序列num[head]~num[tail]利用num[head]作为枢轴,分成两个子序列。
* 且左边序列所有元素的值不大于右边序列所有元素的值。
* 返回值:函数返回枢轴的位置。
*/
int Partition(int num[], int head, int tail)
{
int temp = num[head]; while (head != tail)
{
while (num[tail] >= temp && head != tail)
{
tail--;
}
num[head] = num[tail];
while (num[head] <= temp && head != tail)
{
head++;
}
num[tail] = num[head];
}
num[head] = temp; return head;
} void QuickSort(int num[], int head, int tail)
{
int pivot; pivot = Partition(num, head, tail);
if (head != pivot&&head != pivot - 1)
{
QuickSort(num, head, pivot - 1);
}
if (pivot != tail&&pivot + 1 != tail)
{
QuickSort(num, pivot + 1, tail);
}
} void main()
{
int num[NUM];
int i; for (i = 0; i < NUM; i++)
scanf("%d", num + i); QuickSort(num, 0, NUM - 1); for (i = 0; i < NUM; i++)
printf("%-3d ", num[i]);
}
3.选择排序
3.1 直接选择排序
代码:
/*
* 直接选择排序,由小到大
*/
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#define NUM 10 void SelectSort(int num[], int n)
{
int i, j;
int temp; for (i = 0; i < n - 1; i++)
{
for (j = i + 1; j < n; j++)
{
if (num[i] > num[j])
{
temp = num[i];
num[i] = num[j];
num[j] = temp;
}
}
}
} void main()
{
int num[NUM];
int i; for (i = 0; i < NUM; i++)
scanf("%d", num + i); SelectSort(num, NUM); for (i = 0; i < NUM; i++)
printf("%-3d", num[i]);
}
3.2 堆排序
堆:n个元素序列{k1,k2...ki...kn},当且仅当满足下列关系时称之为堆:
(ki <= k2i,ki <= k2i+1)或者(ki >= k2i,ki >= k2i+1), (i = 1,2,3,4...n/2)
若将和此次序列对应的一维数组(即以一维数组作此序列的存储结构)看成是一个完全二叉树,则堆的含义表明,完全二叉树中所有非终端结点的值均不大于(或不小于)其左、右孩子结点的值。由此,若序列{k1,k2,…,kn}是堆,则堆顶元素(或完全二叉树的根)必为序列中n个元素的最小值(或最大值)。
若在输出堆顶的最小值之后,使得剩余n-1个元素的序列重建一个堆,则得到n个元素中的次小值。如此反复执行,便能得到一个有序序列,这个过程称之为堆排序。
问题:
1. 如何由一个无序序列建成一个堆?
2. 如何在输出堆顶元素之后,调整剩余元素成为一个新的堆?
代码:
/*
* 堆排序,由小到大
* 由小到大排序时,建立的堆为大顶堆;
* 由大到小排序时,建立的堆为小顶堆。
*/
# define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#define NUM 10 /*
* 初始条件:num[root]~num[end]中除了num[root]外均满足堆的定义。
* 函数功能:调整num[root],使得num[root]~num[end]为大顶堆。
*/
void HeapAdjust(int num[],int root,int end)
{
int i;
int temp;
for (i = root * 2 + 1; i <= end; i = 2 * i + 1)
{
if (i + 1 <= end && num[i + 1] > num[i])
{
i++; //i指向左右子结点中的大者
}
if (num[root] >= num[i])
{
break;
}
else
{
temp = num[root];
num[root] = num[i];
num[i] = temp;
root = i;
}
}
} void HeapSort(int num[], int n)
{
int i;
int temp; //将原始无序序列调整为堆。最后一个结点的双亲结点为最后一个非终端结点。故从i=(n-2)/2开始建堆。
for (i = (n - 2) / 2; i >= 0; i--)
{
HeapAdjust(num, i, n - 1);
} //将堆顶元素(未排序中的最大值)和未排序的最后一个元素交换位置;之后重新建堆。
for (i = n - 1; i >= 1; i--)
{
temp = num[i];
num[i] = num[0];
num[0] = temp;
HeapAdjust(num, 0, i - 1);
}
} void main()
{
int num[NUM];
int i; for (i = 0; i < NUM; i++)
scanf("%d", num + i); HeapSort(num, NUM); for (i = 0; i < NUM; i++)
printf("%-3d ", num[i]);
}
4.归并排序
4.1二路归并排序
归并:将两个(或两个以上)有序表合并成一个新的有序表。
假设初始序列含有n个记录,则可以看成是n个有序的子序列,每个子序列的长度为1,然而两两归并,得到[n/2]([x]表示不小于x的最小整数)个长度为2或1的有序子序列;再两两归并,.....,如此重复,直至得到一个长度为n的有序序列为止。这种排序算法称为2路归并排序。
代码1:(递归形式的归并排序)
/*
* 归并排序,由小到大
*/
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <malloc.h>
#define NUM 10 /*
* 函数功能:将已排好序的序列sourceArr[head~mid]和sourceArr[mid+1~tail]归并在一起,
* 使整个序列有序。最终的有序序列存储在数组targetArr中。
*/
void Merge(int sourceArr[], int targetArr[], int head, int mid, int tail)
{
int i, j, k;
for (i = head,j = mid + 1,k = head; i <= mid && j <= tail; k++)
{
if (sourceArr[i] <= sourceArr[j])
{
targetArr[k] = sourceArr[i++];
}
else
{
targetArr[k] = sourceArr[j++];
}
} if (i <= mid)
{
for (; k <= tail; k++)
{
targetArr[k] = sourceArr[i++];
}
} if (j <= tail)
{
for (; k <= tail; k++)
{
targetArr[k] = sourceArr[j++];
}
}
} /*
* 归并排序(递归):
* 如果head!=tail,则对sourceArr[head~mid]和sourceArr[mid+1~tail]分别进行归并排序,
* 并将排序后的两个序列归并在一起,使整体有序。
*/
void MergeSort(int sourceArr[], int targetArr[], int head, int tail)
{
int mid;
int *tempArr; tempArr = (int *)malloc(sizeof(int)*(tail - head + 1));
if (head == tail)
{
targetArr[head] = sourceArr[head];
}
else
{
mid = (head + tail) / 2;
MergeSort(sourceArr, tempArr, head, mid);
MergeSort(sourceArr, tempArr, mid + 1, tail);
Merge(tempArr, targetArr, head, mid, tail);
}
} void main()
{
int num[NUM];
int i; for (i = 0; i < NUM; i++)
scanf("%d", num + i); MergeSort(num, num, 0, NUM-1); for (i = 0; i < NUM; i++)
printf("%-3d ", num[i]);
}
代码2:(非递归形式的归并排序)
/*
* 归并排序(非递归),由小到大
*/
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <malloc.h>
#define NUM 10 /*
* 将2路有序序列归并为1路。形参中只有sourceArr,没有targetArr。
*/
void Merge(int sourceArr[], int head, int mid, int tail)
{
int i, j, k;
int *targetArr; targetArr = (int *)malloc(sizeof(int)*(tail - head + 1)); for (i = head, j = mid + 1, k = 0; i <= mid&&j <= tail; k++)
{
if (sourceArr[i] > sourceArr[j])
{
targetArr[k] = sourceArr[j++];
}
else
{
targetArr[k] = sourceArr[i++];
}
} if (i <= mid)
{
for (; k < tail - head + 1; k++)
{
targetArr[k] = sourceArr[i++];
}
} if (j <= tail)
{
for (; k < tail - head + 1; k++)
{
targetArr[k] = sourceArr[j++];
}
} for (i = head,k = 0; i <= tail; i++,k++)
{
sourceArr[i] = targetArr[k];
}
} void MergeSort(int num[],int n)
{
int interval;
int head; for (interval = 2; interval <= n; interval *= 2)
{
for (head = 0; head + interval <= n; head += interval)
{
Merge(num, head, head + interval / 2 - 1, head + interval - 1);
}
Merge(num, head, head + interval / 2 - 1, n - 1);//处理head + interval > n的情况
}
Merge(num, 0, interval / 2 - 1, n - 1);//处理interval > n的情况
} void main()
{
int num[NUM];
int i; for (i = 0; i < NUM; i++)
scanf("%d", num + i); MergeSort(num, NUM); for (i = 0; i < NUM; i++)
printf("%-3d ", num[i]);
}
4.2 自然合并排序
自然合并排序是归并排序算法的一种改进。
自然合并排序:对于初始给定的数组,通常存在多个长度大于1的已自然排好序的子数组段。例如,若数组a中元素为{4,8,3,7,1,5,6,2},则自然排好序的子数组段有{4,8},{3,7},{1,5,6},{2}。用一次对数组a的线性扫描就足以找出所有这些排好序的子数组段。然后将相邻的排好序的子数组段两两合并,构成更大的排好序的子数组段({3,4,7,8},{1,2,5,6})。继续合并相邻排好序的子数组段,直至整个数组已排好序。
代码:
/*
* 自然合并排序,由小到大
*/
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <malloc.h>
#define NUM 10 int heads[NUM]; /*
* 扫描数组,将已排好序的子数组段的段首加入数组heads中。
* 函数返回段首的总数。
*/
int check(int num[], int n)
{
int num_of_head = 1;
int i; heads[0] = 0;
for (i = 1; i < n; i++)
{
if (num[i] < num[i - 1])
{
heads[num_of_head++] = i;
}
}
return num_of_head;
} /*
* 将2路有序序列归并为1路。
*/
void Merge(int sourceArr[], int head, int mid, int tail)
{
int i, j, k;
int *targetArr; targetArr = (int *)malloc(sizeof(int)*(tail - head + 1));
for (i = head, j = mid + 1, k = 0; i <= mid&&j <= tail; k++)
{
if (sourceArr[i] > sourceArr[j])
{
targetArr[k] = sourceArr[j++];
}
else
{
targetArr[k] = sourceArr[i++];
}
} for (; i <= mid; k++, i++)
{
targetArr[k] = sourceArr[i];
} for (; j <= tail; k++, j++)
{
targetArr[k] = sourceArr[j];
} for (i = head,k = 0; i <= tail; i++, k++)
{
sourceArr[i] = targetArr[k];
}
} void MergeSort(int num[], int n)
{
int num_of_head;
int i; while (1)
{
num_of_head = check(num, n);
if (num_of_head == 1)
{
break;
}
else
{
for (i = 0; i < num_of_head - 1; i += 2)
{
if (i + 2 <= num_of_head - 1)
{
Merge(num, heads[i], heads[i + 1] - 1, heads[i + 2] - 1);
}
else
{
Merge(num, heads[i], heads[i + 1] - 1, n - 1);
}
}
}
}
} void main()
{
int num[NUM];
int i; for (i = 0; i < NUM; i++)
scanf("%d", num + i); MergeSort(num, NUM); for (i = 0; i < NUM; i++)
printf("%-3d ", num[i]);
}
5.分布排序
5.1 基数排序
第一步
以LSD为例,假设原来有一串数值如下所示:
73, 22, 93, 43, 55, 14, 28, 65, 39, 81
首先根据个位数的数值,在走访数值时将它们分配至编号0到9的桶子中:
0 |
|
1 |
81 |
2 |
22 |
3 |
73 93 43 |
4 |
14 |
5 |
55 65 |
6 |
|
7 |
|
8 |
28 |
9 |
39 |
第二步
接下来将这些桶子中的数值重新串接起来,成为以下的数列:
81, 22, 73, 93, 43, 14, 55, 65, 28, 39
接着再进行一次分配,这次是根据十位数来分配:
0 |
|
1 |
14 |
2 |
22 28 |
3 |
39 |
4 |
43 |
5 |
55 |
6 |
65 |
7 |
73 |
8 |
81 |
9 |
93 |
第三步
接下来将这些桶子中的数值重新串接起来,成为以下的数列:
14, 22, 28, 39, 43, 55, 65, 73, 81, 93
这时候整个数列已经排序完毕;如果排序的对象有三位数以上,则持续进行以上的动作直至最高位数为止。
LSD的基数排序适用于位数小的数列,如果位数多的话,使用MSD的效率会比较好。MSD的方式与LSD相反,是由高位数为基底开始进行分配,但在分配之后并不马上合并回一个数组中,而是在每个“桶子”中建立“子桶”,将每个桶子中的数值按照下一数位的值分配到“子桶”中。在进行完最低位数的分配后再合并回单一的数组中。
代码1(LSD):
/*
* 基数排序,由小到大。
* 假设待排序数最多只有3位数。
* 最低位优先基数排序(LSD)
*/
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <malloc.h>
#include <string.h> #define NUM 10 /*
* 用于获取整数num的个位、十位、或者百位
*/
int getdigit(int num, int power)
{
int result; switch (power)
{
case 1:result = num % 10; break; //个位
case 2:result = num % 100 / 10; break; //十位
case 3:result = num / 100; break; //百位
}
return result;
} void RadixSort(int num[], int n)
{
int count[10] = {0};
int *bucket;
int i;
int key;
int digit; bucket = (int *)malloc(sizeof(int) * n); //key从1到3表示,依次比较个位、十位、百位。
for (key = 1; key <= 3; key++)
{
//key=1时,count[0~9]分别表示个位数为0,1...,9的元素的数量
for (i = 0; i < n; i++)
{
digit = getdigit(num[i], key);
count[digit]++;
} //key=1时,count[i]表示个位数为0~i的元素的总数量
for (i = 1; i < 10; i++)
{
count[i] = count[i] + count[i - 1];
} //从后往前遍历序列,将元素放入对应的子桶中。从后往前是为了保证稳定性。
for (i = n - 1; i >= 0; i--)
{
digit = getdigit(num[i], key);
bucket[--count[digit]] = num[i];
} for (i = 0; i < n; i++)
{
num[i] = bucket[i];
} //count数组清零。
memset(count, 0, sizeof(int) * 10);
}
} void main()
{
int num[NUM];
int i; for (i = 0; i < NUM; i++)
scanf("%d", num + i); RadixSort(num, NUM); for (i = 0; i < NUM; i++)
printf("%-3d ", num[i]);
}
代码2(MSD):
/*
* 基数排序,由小到大。
* 假设元素最高位3位数。
* 最高位优先排序(MSD)。
*/
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <malloc.h>
#include <string.h> #define NUM 10 int getdigit(int num, int power)
{
int result; switch (power)
{
case 1:result = num % 10; break;
case 2:result = num % 100 / 10; break;
case 3:result = num / 100; break;
} return result;
} void RadixSort(int num[], int head,int tail,int key)
{
int i,j;
int digit;
int *bucket;
int count[10] = {0};
int count_backup[10];
int left, right; bucket = (int*)malloc(sizeof(int)*(tail - head + 1)); for (i = head; i <= tail; i++)
{
digit = getdigit(num[i], key);
count[digit]++;
} for (i = 1; i < 10; i++)
{
count[i] = count[i] + count[i - 1];
} memcpy(count_backup, count, sizeof(int) * 10); //备份count数组中的数据 for (i = tail; i >= head; i--)
{
digit = getdigit(num[i], key);
bucket[--count[digit]] = num[i];
} for (i = head, j = 0; i <= tail; i++, j++)
{
num[i] = bucket[j];
} free(bucket); if(key != 1)
{
//对每个子桶中的数据分别按下一位进行基数排序。
key--;
if (count_backup[0] != 0 && count_backup[0] != 1)
{
RadixSort(num, head, head + count_backup[0] - 1, key);
}
for (i = 0; i <= 8; i++)
{
left = head + count[i];
right = head + count[i + 1] - 1; if (left < right)
{
RadixSort(num, left, right, key);
}
}
}
} void main()
{
int num[NUM];
int i; for (i = 0; i < NUM; i++)
scanf("%d", num + i); RadixSort(num, 0, NUM - 1, 3); for (i = 0; i < NUM; i++)
printf("%-3d ", num[i]);
}
pdf版下载:http://pan.baidu.com/s/1bn1XL3T
工程文件打包下载:http://pan.baidu.com/s/1pJqegyf (开发环境为visual studio 2013)