点击进入–>数据结构与算法可视化
排序算法
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define ARRAYSIZE 1000 /*数组长度 */
1. 直接插入排序算法 （重点）
跟斗地主摸牌然后插入手牌差不多,每次将待排序的记录（摸的牌）插入到已经排好序的文件当中（有序的手牌）
1.1 带哨位
//直接插入排序算法
void insertSort (int array[ ], int length)
{
int i, j;
for(i=2;i<=n;i++) //array[0]作为哨位，而array[1]作为第一张手牌无需比较
{
array[0]=array[i];//哨兵上岗,是array[i]的副本
j=i-1; //待比较的值
while(array[0]<array[j]){ //从右至左在有序区array[1..i-1]中查找array[i]的插入位置
array[j+1]=array[j]; //逐一后移
j--;
}
array[j+1]=array[0]; //将array[i]插入
}
}
1.2 不带哨位
void insertSort (int array[ ], int length){
for(int i=1;i<length;i++){
int temp = array[i];
int j;
for(j=i-1;j>=0;j++){
if(array[j]>temp)
array[j+1]=array[j];
else
break;
}
array[j+1]=temp;
}
}
哨兵的作用：
1.保存array[i]的副本，防止记录后移丢失array[i]
2.用于监视j是否越界（省略了循环判定条件j≥1)）
2. 希尔排序算法 （重点）
同样是摸牌排序，但是此时是n个人摸牌（n=增量），每个人给自己的手牌排序（直接插入排序），最终将n个人的牌放到一起
//希尔排序算法
void shellSort (int r[ ], int n)
{ int i,j,d;
for (d=n/2; d>=1; d=d/2)
{
for (i=d+1; i<=n; i++) //将r[i]插入到所属的子序列中
{
r[0]=r[i]; //暂存待插入记录
j=i-d; //j指向所属子序列的最后一个记录
while (j>0 && r[0]<r[j])
{
r[j+d]=r[j]; //记录后移d个位置
j=j-d; //比较同一子序列的前一个记录
}
r[j+d]=r[0];
}
//displayArray(r,n); //调试用，便于查看中间结果
}
}
3. 冒泡排序算法 （基本交换排序）（重点）
从“最下面”的一个泡泡开始，如果它比上一个泡泡大（小），则让它上浮（交换顺序）
//冒泡排序算法
void bubbleSort(int r[ ], int n)
{
for(int i=0;i<n-1;i++)
for(int j=0;j<n-i-1;j++){
if(r[j]>r[j+1]){
int temp=r[j];
r[j]=r[j+1];
r[j+1]=temp;
}
}
}
4. 快速排序算法 （重点）
原理：
- 任意选择一个基准点
- 从右向左遍历序列，若存在比基准点小的，则将其与基准点交换
- 从左向右遍历序列，若存在比基准点大的，则将其与基准点交换
- 重复2-3操作
void quickSort(int array[],int low,int high)
{
int i,j;
int key;
if(low>high)
return;
i=low;
j=high;
key=array[low]; //将左侧的数作为基准点
//先对右侧的进行遍历
while(i!=j){
while(array[j]>=key&&i<j){
j--;
}
while(array[i]<=key&&i<j){
i++;
}
if(i<j){ //交换i、j对应的值
int temp;
temp=array[i];
array[i]=array[j];
array[j]=temp;
}
}
//当i=j跳出循环
//重合点作为新的基准值
array[low] = array[i]; //新的基准值放到low位置
array[i] = key; //旧的基准值放在重合点
//以重合点为界，对左右划分进行递归快排
quickSort(array,low,i-1);
quickSort(array,i+1,high);
}
//初次调用的时候，low=1，high=array.length
5. 选择排序
从整个序列中找到最小（大）的一个，让它与当前位置的元素交换（也是待排序序列–>有序序列）
不断重复上述过程
//选择排序
void selectSort(int r[],int n)
{
int i,j,d=0;
for(i=1;i<n;i++)
{
d = i;
for(j=i+1;j<=n;j++)
{
if(r[j]<r[d]) d=j;
}
if(d!=i) {r[0]=r[i];r[i]=r[d];r[d]=r[0];}//swap(&k[i],&k[d]);
//displayArray(r,n); //调试用，便于查看中间结果
}
}
6. 堆排序算法
大根堆：根节点比左右子节点大
小根堆：根节点比左右子节点小
小根堆筛选法堆调整：
从树的最右下方的子树开始，将该子树调整为小根堆（根节点比左右子节点小）
从下往上、从右往左重复操作直至到达根节点
从上往下检查小根堆
6.1 堆调整
void shift ( int r[ ], int k, int m )
{ int i,j;
int temp;
//要筛选结点的编号为k，堆中最后一个结点的编号为m
i=k; j=2*i; temp=r[i]; //将筛选记录暂存
while (j<=m ) //筛选还没有进行到叶子
{
if (j<m && r[j]<r[j+1]) j++; //左右孩子中取较大者
if (temp >r[j]) break;
else {
r[i]=r[j]; i=j; j=2*i;
}
}
r[i]=temp; //将筛选记录移到正确位置
}
6.2 堆排序
void heapSort ( int r[], int n)
{
int i,j;
for (i=n/2; i>=1; i--) //初建堆
shift(r, i, n) ;
//displayArray(r,n);
for (i=1; i<n; i++ )
{ j = n-i+1;
r[0]=r[1];r[1]=r[j];r[j]=r[0];; //移走堆顶
shift(r, 1, n-i); //重建堆
//displayArray(r,n); //调试用，便于查看中间结果
}
}
7. 归并
将n个序列单独拿出来排序，最终合并
比如二路归并
1 3 5 4 9 7
(1 3) (4 5) (7 9)
7.1 归并相邻两个子序列
//归并相邻两个子序列
void Merge (int r[ ], int r1[ ], int s, int m, int t )
{ int i,j,k;
i=s; j=m+1; k=s;
while (i<=m && j<=t)
{
if (r[i]<=r[j]) r1[k++]=r[i++];
else r1[k++]=r[j++];
}
if (i<=m) while (i<=m) //收尾处理
r1[k++]=r[i++]; //前一个子序列
else while (j<=t)
r1[k++]=r[j++]; //后一个子序列
}
7.2 一趟二路归并
//一趟二路归并
void MergePass (int r[ ], int r1[ ], int n, int h)
{
int i=1,k=1;
while (i <= n-2*h+1) //情况1
{
Merge (r, r1, i, i+h-1,i+2*h-1);
i+=2*h;
}
if (i< n-h+1) Merge (r, r1, i,i+h-1, n); //情况2
else for (k=i; k<=n; k++) //情况3
r1[k]=r[k];
}
7.3 二路归并
//二路归并排序算法
void MergeSort (int r[ ], int r1[ ], int n )
{ int h;
h=1;
while (h<n)
{
MergePass (r, r1, n, h);
h=2*h;
//displayArray(r1,n); //调试用，便于查看中间结果
MergePass (r1, r, n, h);
h=2*h;
//displayArray(r,n); //调试用，便于查看中间结果
}
}
京公网安备 11010502036488号