#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define ARRAYSIZE 1000 /*数组长度 */
跟斗地主摸牌然后插入手牌差不多,每次将待排序的记录(摸的牌)插入到已经排好序的文件当中(有序的手牌)
//直接插入排序算法
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]插入
}
}
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))
同样是摸牌排序,但是此时是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); //调试用,便于查看中间结果
}
}
从“最下面”的一个泡泡开始,如果它比上一个泡泡大(小),则让它上浮(交换顺序)
//冒泡排序算法
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;
}
}
}
原理:
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
从整个序列中找到最小(大)的一个,让它与当前位置的元素交换(也是待排序序列–>有序序列) 不断重复上述过程
//选择排序
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); //调试用,便于查看中间结果
}
}
大根堆:根节点比左右子节点大 小根堆:根节点比左右子节点小
小根堆筛选法堆调整: 从树的最右下方的子树开始,将该子树调整为小根堆(根节点比左右子节点小) 从下往上、从右往左重复操作直至到达根节点 从上往下检查小根堆
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; //将筛选记录移到正确位置
}
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); //调试用,便于查看中间结果
}
}
将n个序列单独拿出来排序,最终合并 比如二路归并 1 3 5 4 9 7 (1 3) (4 5) (7 9)
//归并相邻两个子序列
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++]; //后一个子序列
}
//一趟二路归并
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];
}
//二路归并排序算法
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); //调试用,便于查看中间结果
}
}