/*
===============================================
作者：rerli
时刻：2003-12-15
意图：重温经典排序思维，并用C言语指针完结排序算法
================================================
*/
/*
=============================================================================
相关常识介绍(一切界说只为协助读者了解相关概念，并非严厉界说)：
1、安稳排序和非安稳排序
简略地说便是一切持平的数经过某种排序办法后，仍能坚持它们在排序之前的相对次第，咱们就
说这种排序办法是安稳的。反之，便对错安稳的。
比方：一组数排序前是a1,a2,a3,a4,a5，其间a2=a4，经过某种排序后为a1,a2,a4,a3,a5，
则咱们说这种排序是安稳的，由于a2排序前在a4的前面，排序后它仍是在a4的前面。假定变成a1,a4,
a2,a3,a5就不是安稳的了。
2、内排序和外排序
在排序进程中，一切需求排序的数都在内存，并在内存中调整它们的存储次序，称为内排序;
在排序进程中，只要部分数被调入内存，并凭借内存调整数在外存中的寄存次序排序办法称为外排序。
3、算法的时刻复杂度和空间复杂度
所谓算法的时刻复杂度，是指履行算法所需求的核算工作量。
一个算法的空间复杂度，一般是指履行这个算法所需求的内存空间。
================================================================================
*/
/*
================================================
功用：挑选排序
输入：数组称号(也便是数组首地址)、数组中元素个数
================================================
*/
/*
====================================================
算法思维简略描绘：
在要排序的一组数中，选出最小的一个数与榜首个方位的数交流;
然后在剩余的数傍边再找最小的与第二个方位的数交流，如此循环
到倒数第二个数和最终一个数比较停止。
挑选排序是不安稳的。算法复杂度O(n2)–[n的平方]
=====================================================
*/
void select_sort(int *x, int n)
{
int i, j, min, t;
for (i=0; i {
min = i; /*假定当时下标为i的数最小，比较后再调整*/
for (j=i+1; j {
if (*(x+j) < *(x+min))
{
min = j; /*假如后边的数比前面的小，则记下它的下标*/
}
}
if (min != i) /*假如min在循环中改变了，就需求交流数据*/
{
t = *(x+i);
*(x+i) = *(x+min);
*(x+min) = t;
}
}
}
/*
================================================
功用：直接刺进排序
输入：数组称号(也便是数组首地址)、数组中元素个数
================================================
*/
/*
====================================================
算法思维简略描绘：
在要排序的一组数中，假定前面(n-1) [n>=2] 个数已经是排
好次序的，现在要把第n个数插到前面的有序数中，使得这n个数
也是排好次序的。如此重复循环，直到悉数排好次序。
直接刺进排序是安稳的。算法时刻复杂度O(n2)–[n的平方]
=====================================================
*/
void insert_sort(int *x, int n)
{
int i, j, t;
for (i=1; i {
/*
暂存下标为i的数。留意：下标从1开端，原因便是开端时
榜首个数即下标为0的数，前面没有任何数，单单一个，以为
它是排好次序的。
*/
t=*(x+i);
for (j=i-1; j>=0 && t<*(x+j); j–) /*留意：j=i-1，j–，这儿便是下标为i的数，在它前面有序列中找刺进方位。*/
{
*(x+j+1) = *(x+j); /*假如满意条件就往后挪。最坏的状况便是t比下标为0的数都小，它要放在最前面，j==-1，退出循环*/
}
*(x+j+1) = t; /*找到下标为i的数的放置方位*/
}
}
/*
================================================
功用：冒泡排序
输入：数组称号(也便是数组首地址)、数组中元素个数
================================================
*/
/*
====================================================
算法思维简略描绘：
在要排序的一组数中，对当时还未排好序的规模内的悉数数，自上
而下对相邻的两个数顺次进行比较和调整，让较大的数往下沉，较
小的往上冒。即：每逢两相邻的数比较后发现它们的排序与排序要
求相反时，就将它们交流。
下面是一种改善的冒泡算法，它记载了每一遍扫描后最终下沉数的
方位k，这样能够削减外层循环扫描的次数。
冒泡排序是安稳的。算法时刻复杂度O(n2)–[n的平方]
=====================================================
*/
void bubble_sort(int *x, int n)
{
int j, k, h, t;
for (h=n-1; h>0; h=k) /*循环到没有比较规模*/
{
for (j=0, k=0; j {
if (*(x+j) > *(x+j+1)) /*大的放在后边，小的放到前面*/
{
t = *(x+j);
*(x+j) = *(x+j+1);
*(x+j+1) = t; /*完结交流*/
k = j; /*保存最终下沉的方位。这样k后边的都是排序排好了的。*/
}
}
}
}
/*
================================================
功用：希尔排序
输入：数组称号(也便是数组首地址)、数组中元素个数
================================================
*/
/*
====================================================
算法思维简略描绘：
在直接刺进排序算法中，每次刺进一个数，使有序序列只添加1个节点，
而且对刺进下一个数没有供给任何协助。假如比较相隔较远间隔(称为
增量)的数，使得数移动时能跨过多个元素，则进行一次比较就或许消除
多个元素交流。D.L.shell于1959年在以他姓名命名的排序算法中完结
了这一思维。算法先即将排序的一组数按某个增量d分红若干组，每组中
记载的下标相差d.对每组中悉数元素进行排序，然后再用一个较小的增量
对它进行，在每组中再进行排序。当增量减到1时，整个要排序的数被分红
一组，排序完结。
下面的函数是一个希尔排序算法的一个完结，初度取序列的一半为增量，
今后每次折半，直到增量为1。
希尔排序是不安稳的。
=====================================================
*/
void shell_sort(int *x, int n)
{
int h, j, k, t;
for (h=n/2; h>0; h=h/2) /*操控增量*/
{
for (j=h; j {
t = *(x+j);
for (k=j-h; (k>=0 && t<*(x+k)); k-=h)
{
*(x+k+h) = *(x+k);
}
*(x+k+h) = t;
}
}
}
/*
================================================
功用：快速排序
输入：数组称号(也便是数组首地址)、数组中起止元素的下标
================================================
*/
/*
====================================================
算法思维简略描绘：
快速排序是对冒泡排序的一种实质改善。它的基本思维是经过一趟
扫描后，使得排序序列的长度能大幅度地削减。在冒泡排序中，一次
扫描只能确保最大数值的数移到正确方位，而待排序序列的长度或许只
削减1。快速排序经过一趟扫描，就能确保某个数(以它为基准点吧)
的左面各数都比它小，右边各数都比它大。然后又用相同的办法处理
它左右两头的数，直到基准点的左右只要一个元素停止。它是由
C.A.R.Hoare于1962年提出的。
明显快速排序能够用递归完结，当然也能够用栈化解递归完结。下面的
函数是用递归完结的，有爱好的朋友能够改成非递归的。
快速排序是不安稳的。最理想状况算法时刻复杂度O(nlog2n)，最坏O(n2)
=====================================================
*/
void quick_sort(int *x, int low, int high)
{
int i, j, t;
if (low < high) /*要排序的元素起止下标，确保小的放在左面，大的放在右边。这儿以下标为low的元素为基准点*/
{
i = low;
j = high;
t = *(x+low); /*暂存基准点的数*/
while (i {
while (it) /*在右边的只要比基准点大仍放在右边*/
{
j–; /*前移一个方位*/
}
if (i {
*(x+i) = *(x+j); /*上面的循环退出：即呈现比基准点小的数，替换基准点的数*/
i++; /*后移一个方位，并以此为基准点*/
}
while (i {
i++; /*后移一个方位*/
}
if (i {
*(x+j) = *(x+i); /*上面的循环退出：即呈现比基准点大的数，放到右边*/
j–; /*前移一个方位*/
}
}
*(x+i) = t; /*一遍扫描完后，放到恰当方位*/
quick_sort(x,low,i-1); /*对基准点左面的数再履行快速排序*/
quick_sort(x,i+1,high); /*对基准点右边的数再履行快速排序*/
}
}
/*
================================================
功用：堆排序
输入：数组称号(也便是数组首地址)、数组中元素个数
================================================
*/
/*
====================================================
算法思维简略描绘：
堆排序是一种树形挑选排序，是对直接挑选排序的有用改善。
堆的界说如下：具有n个元素的序列(h1,h2,…,hn),当且仅当
满意(hi>=h2i,hi>=2i+1)或(hi<=h2i,hi<=2i+1)(i=1,2,…,n/2)
时称之为堆。在这儿只评论满意前者条件的堆。
由堆的界说能够看出，堆顶元素(即榜首个元素)必为最大项。彻底二叉树能够
很直观地表明堆的结构。堆顶为根，其它为左子树、右子树。
初始时把要排序的数的序列看作是一棵次序存储的二叉树，调整它们的存储次序，
使之成为一个堆，这时堆的根节点的数最大。然后将根节点与堆的最终一个节点
交流。然后对前面(n-1)个数从头调整使之成为堆。依此类推，直到只要两个节点
的堆，并对它们作交流，最终得到有n个节点的有序序列。
从算法描绘来看，堆排序需求两个进程，一是树立堆，二是堆顶与堆的最终一个元素
交流方位。所以堆排序有两个函数组成。一是建堆的浸透函数，二是重复调用浸透函数
完结排序的函数。
堆排序是不安稳的。算法时刻复杂度O(nlog2n)。
*/
/*
功用：浸透建堆
输入：数组称号(也便是数组首地址)、参加建堆元素的个数、从第几个元素开端
*/
void sift(int *x, int n, int s)
{
int t, k, j;
t = *(x+s); /*暂存开端元素*/
k = s; /*开端元素下标*/
j = 2*k + 1; /*右子树元素下标*/
while (j {
if (j {
j++;
}
if (t<*(x+j)) /*调整*/
{
*(x+k) = *(x+j);
k = j; /*调整后，开端元素也随之调整*/
j = 2*k + 1;
}
else /*没有需求调整了，已经是个堆了，退出循环。*/
{
break;
}
}
*(x+k) = t; /*开端元素放到它正确方位*/
}
/*
功用：堆排序
输入：数组称号(也便是数组首地址)、数组中元素个数
*/
void heap_sort(int *x, int n)
{
int i, k, t;
int *p;
for (i=n/2-1; i>=0; i–)
{
sift(x,n,i); /*初始建堆*/
}
for (k=n-1; k>=1; k–)
{
t = *(x+0); /*堆顶放到最终*/
*(x+0) = *(x+k);
*(x+k) = t;
sift(x,k,0); /*剩余的数再建堆*/
}
}
void main()
{
#define MAX 4
int *p, i, a[MAX];
/*录入测验数据*/
p = a;
printf("Input %d number for sorting :\n",MAX);
for (i=0; i {
scanf("%d",p++);
}
printf("\n");
/*测验挑选排序*/
p = a;
select_sort(p,MAX);
/**/
/*测验直接刺进排序*/
/*
p = a;
insert_sort(p,MAX);
*/
/*测验冒泡排序*/
/*
p = a;
insert_sort(p,MAX);
*/
/*测验快速排序*/
/*
p = a;
quick_sort(p,0,MAX-1);
*/
/*测验堆排序*/
/*
p = a;
heap_sort(p,MAX);
*/
for (p=a, i=0; i {
printf("%d ",*p++);
}
printf("\n");
system("pause");
}
