多个经典的排序算法及代码

冒泡排序，插入排序，shell排序，快速排序，堆排序等

// Sort.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#define MAX 10

void GetRandom(int a[],int n)
{
for (int i=0; i{
a[i]=rand()%(2*n);
}
}

void Print(int a[], int n)
{
for(int i=0; iprintf("%d,",a[i]);
printf("\n");
}


void InsertSort(int a[], int n)
{
int i;

for(i=1;i{
if (a[i]{
int key = a[i];
int j;

for(j=i-1; j>=0&&a[j]>key; j--)//将大于a[i]的元素后移
{
a[j+1]=a[j];
}
a[j+1]=key;//不要写成a[j]！！！
}
}
}

void ShellSort(int a[], int n)
{
int d;

for (d=n/2; d>=1; d/=2)//间距从n/2一直除2到1
{
//间距为d的元素为一组，组内插入排序
//这一段就是把InsertSort中的1换成d
for(int i=d; i{
if (a[i]{
int key=a[i];
int j;

for(j=i-d; j>=0&&a[j]>key; j-=d)
{
a[j+d]=a[j];
}
a[j+d]=key;
}
}
}
}

void BubbleSort(int a[], int n)
{
for(int i=n-1; i>0; i--)
{
int flagExchange=0;//每一趟是否发生交换

for(int j=0; j{
if (a[j]>a[j+1])
{
int temp=a[j];
a[j]=a[j+1];
a[j+1]=temp;
flagExchange=1;
}
}

if (!flagExchange)//如果某一趟已经没有发生交换，直接推出
{
break;
}
}
}

int Partition(int a[], int low, int high)
{
int key=a[low];

while(low{
for(;low=key;high--);//千万不要忘了=号！！！
a[low]=a[high];
for(;lowa[high]=a[low];
}

a[low]=key;

return low;
}

void _QuickSort(int a[], int low, int high)
{
if(low{
int mid = Partition(a,low,high);
_QuickSort(a,low,mid-1);
_QuickSort(a,mid+1,high);
}
}

void QuickSort(int a[], int n)
{
_QuickSort(a,0,n-1);
}

void SelectSort(int a[], int n)
{
for(int i=0; i{
int k=i;//每一趟最小值的索引
for(int j=i+1; j{
if (a[j]{
k=j;
}
}

if (k!=i)
{
int temp=a[k];
a[k]=a[i];
a[i]=temp;
}
}

}

//a[0]不用，最小的在a[1],小顶堆
void InsertHeap(int a[],int *heapsize, int newVal)
{
(*heapsize)++;

int i;
for(i=*heapsize; i/2>0&&a[i/2]>newVal; i/=2)
{
a[i]=a[i/2];
}
a[i]=newVal;

Print(a,*heapsize+1);
}



//删除a[1]，小顶堆
int DeleteHeapHead(int a[], int *heapsize)
{
int min=a[1];
int last=a[*heapsize];
(*heapsize)--;

int i;
int m;

for(i=1; 2*i<(*heapsize); i=m)
{
m=2*i;

//m为最小子数的索引
if (m!=*heapsize && a[m+1]m++;

if (a[m]>last)
{
break;
}
else
{
a[i]=a[m];
}
}

a[i]=last;

Print(a,*heapsize+1);

return min;
}

//小顶堆
void HeapSort(int a[], int n)
{
int* heap=new int[n+1];
int heapsize=0;

for( int i=0; i{
heap[i]=0;
}

for(int i=0; i{
InsertHeap(heap,&heapsize,a[i]);
}

for(int i=0; i{
a[i]=DeleteHeapHead(heap,&heapsize);
}

delete[] heap;
}

//从a[0]开始，大顶堆（把它当成从1开始的想，写出来后，[]内的都减1就可以了。）
void InsertHeap2(int a[], int *heapsize, int newVal)
{
(*heapsize)++;

int i;
for(i=*heapsize; i/2>0&&a[i/2-1]{
a[i-1]=a[i/2-1];
}
a[i-1]=newVal;

Print(a,*heapsize);
}

//删除最小的a[0]，大顶堆
void DeleteHeapHead2(int a[], int *heapsize)
{
int max=a[0];
int last=a[*heapsize-1];
(*heapsize)--;

int i;
int m;

for(i=1; 2*i<(*heapsize); i=m)
{
m=2*i;

//m为最小子数的索引
if (m!=*heapsize && a[m]>a[m-1])
m++;

if (a[m-1]{
break;
}
else
{
a[i-1]=a[m-1];
}
}

a[i-1]=last;
a[*heapsize]=max;

Print(a,MAX);
}

//大顶堆
void HeapSort2(int a[], int n)
{
int heapsize=0;

for(int i=0; i{
InsertHeap2(a,&heapsize,a[i]);
}

for(int i=0; i{
DeleteHeapHead2(a,&heapsize);
}
}

void MergeSort(int a[], int n)
{

}

int _tmain(int argc, _TCHAR* argv[])
{
int a[MAX];

printf("test of InsertSort\n");
GetRandom(a,MAX);
Print(a,MAX);
InsertSort(a,MAX);
Print(a,MAX);

printf("test of ShellSort\n");
GetRandom(a,MAX);
Print(a,MAX);
ShellSort(a,MAX);
Print(a,MAX);

printf("test of BubbleSort\n");
GetRandom(a,MAX);
Print(a,MAX);
BubbleSort(a,MAX);
Print(a,MAX);

printf("test of QuickSort\n");
GetRandom(a,MAX);
Print(a,MAX);
QuickSort(a,MAX);
Print(a,MAX);

printf("test of SelectSort\n");
GetRandom(a,MAX);
Print(a,MAX);
SelectSor

t(a,MAX);
Print(a,MAX);

printf("test of HeapSort\n");
GetRandom(a,MAX);
Print(a,MAX);
HeapSort(a,MAX);
Print(a,MAX);

printf("test of HeapSort2\n");
GetRandom(a,MAX);
Print(a,MAX);
HeapSort2(a,MAX);
Print(a,MAX);

return 0;
}