数据结构算法整理-07-排序算法

#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;
	}
}

//希尔排序算法 
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);   //调试用，便于查看中间结果 
    }
}

//归并相邻两个子序列 
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); //调试用，便于查看中间结果
    }
}