一些排序算法
[size=2]写这个是为了提高自已对排序算法的理解,以前也有写,不过是分散写,没有像这样统一写在一个文件里.这次没有写归并,基数排序,近期内再补上吧.
代码较长,不过比较容易看得懂,呵呵.发上来给大家批评指证吧.如果大家发现有什么问题,或觉得哪里应该改进,请回帖告诉我,感激万分.
本代码使用的高亮软件是雨中飞燕之作:"HighlightCodeV3.0 software by yzfy(雨中飞燕) http:// **"
[size=2]
[/color]#include<iostream>
#include<ctime>
#define Swap(i,j) {int s = (i); (i) = (j); (j) = s;}
const int MAXSIZE = 30;
int array[MAXSIZE];
/*直接插入排序
基本思想:当插入第I个元素时,前面的V[0],V[1]....V[I-1]已经排好序,这时用V[I]的排序码与
V[I-1],V[I-2]....的排序码进行比较,找到插入位置即将V[I]插入,原来位置上的元素向后移.
*/
void InsertSort(int (&array)[MAXSIZE],const int left,int const right)
{
for (int i=left+1;i<=right;i++)
{
if (array[i] < array[i-1])
{
int temp = array[i], j = i-1;
do
{
array[j+1] = array[j]; j--;
}
while (j >= left && temp < array[j]);
array[j+1] = temp;
}
}
}
/*折半插入排序(二分法插入排序)
基本思想:设在数据表中有一个元素序列V[0],V[1]...V[n-1].其中V[0],V[1]...V[I-1]
是已经排好序的元素.在插入V[I]时,得用折半搜索寻找V[I]的插入位置.
*/
void BinaryInsertSort(int (&array)[MAXSIZE],int left,int right)
{
for (int i=left+1;i<=right;i++)
{
int temp = array[i];
while (left<=right)
{
int middle = (left+right)/2;
if (temp < array[i]) right = middle - 1;
else left = middle + 1;
}
for (int k=i-1;k>=left;k--) array[k+1] = array[k];
array[left] = temp;
}
}
/*希尔排序(SHELL SORT),又称缩小增量排序(diminishing-increment sort)
基本思想:设待排序元素序列有N个元素,首先取出一个整数gap<n作为间隔,将全部元素分为gap
个字序列,所有距离为gap的元素放在同一个子序列中,在每一个子序列中分别施行直接插入排序.
然后缩小间隔gap,直到gap等于 1
*/
void ShellSort(int (&array)[MAXSIZE],const int left,const int right)
{
int gap = right-left+1; //增量的初始值
do
{
gap = gap/3 + 1; // 求下一增量
for (int i=(left+gap);i<=right;i++) //各子充列交错处理
if (array[i] < array[i-gap]) //逆序
{
int temp = array[i], j = i-gap;
do
{
array[j+gap] = array[j]; //后移元素
j = j-gap; //现比较前一元素
}while (j>left &&temp < array[j]);
}
}while (gap > 1);
}
/*快速排序
快速排序采用分治法(divide-and-conquer)进行排序.
基本思想:任取待排序元素序列中某个元素作基准,按照该元素排序码大小,将整个元素序列划分为左右两个
子序列,左侧都比基准元素小,右侧则大于或等于.然后分别对这两个子序列重复施行上述方法,直到所有的元素
都排在相应位置为止
*/
//快速排序的划分
int Partition(const int left,const int right)
{
int pivotpos = left,pivot = array[left]; //基准元素
for (int i=left+1;i<=right;i++)
if (array[i] <pivot)
{
pivotpos++;
if (pivotpos != i) Swap(array[pivotpos],array[i]);
}
array[left] = array[pivotpos];
array[pivotpos] = pivot;
return pivotpos;
}
//快速排序
void QuickSort(int(&array)[MAXSIZE],const int left,const int right)
{
if (right-left <= 25) InsertSort(array,0,MAXSIZE-1); //数据规模较小时,采用直接插入.
else
{
int pivotpos = Partition(left,right);
QuickSort(array,left,pivotpos-1);
QuickSort(array,pivotpos+1,right);
}
}
//三路划分的快速排序算法
void Quick_Sort(int (&array)[MAXSIZE],int low,int high)
{
int pivot=array[low];
if (low >= high) return;
while (low<high)
{
while (low<high && pivot<array[high]) high--;
if (low<high)
{
array[low]=array[high];
low++;
}
while (low<high && pivot>=array[low]) low++;
if (low<high)
{
array[high]=array[low];
high++;
}
}
array[low]=pivot;
Quick_Sort(array,low,low-1);
Quick_Sort(array,low+1,high);
}
/*
选择排序
基本思想:每一趟(纺织品如第 I 趟,I = 0,1,2,...N-2)在后面 N-I个待排序元素中选出排序码
最小的元素,作为有序元素序列的第 I 个元素.待到第 N-2趟作完,待排序元素只剩下 1 个,就不用再选了.
*/
//直接选择排序
void SelectSort(int (&array)[MAXSIZE],const int left,const int right)
{
for (int i=left;i<right;i++)
{
int k = i;
for (int j=i+1;j<=right;j++)
if (array[j] < array[k]) k = j; //当前最小排序码的元素
if (k != i) Swap(array[i],array[k]);
}
}
/*
堆排序
(1):根据初始输入数据,得用堆的调整算法SiftDown()形成堆
(2):通过一系列的元素交换和重新调整堆进行排序
*/
//堆调整
void MaxHeap_SiftDown(int (&heap)[MAXSIZE],const int start,const int end)
{
int i=start,temp = heap[start], j = 2*start + 1;
while (j <= end) //检查是否到最后位置
{
if (j < end && heap[j] < heap[j+1]) j++;
if (temp >= heap[j]) break;
else //子女中大者上移
{
heap[i] = heap[j];
i = j; //i下降到子女位置
j = 2*j + 1;
}
}
heap[i] = temp; //将temp中元素放到适合位置
}
//堆排序
void HeapSort(int (&heap)[MAXSIZE],const int size)
{
for (int i=(size-2)/2;i>=0;i--)
MaxHeap_SiftDown(heap,i,size-i);
for (int j=size-1;j>=0;j--)
{
Swap(heap[0],heap[j]);
MaxHeap_SiftDown(heap,0,j-1);
}
}
//输出排序后的数列
void display(int (&array)[MAXSIZE],int size)
{
for (int i=0;i<size;i++)
{
std::cout<<array[i]<<" ";
if ((i+1)%10 == 0) std::cout<<std::endl;
}
}
int main(void)
{
srand(unsigned(time(NULL)));
for (int i=0;i<MAXSIZE;i++)
array[i] = rand()%10000;
std::cout<<"***直接插入排序***"<<std::endl;
InsertSort(array,0,MAXSIZE-1);
display(array,MAXSIZE);
std::cout<<std::endl<<"***折半插入排序(二分法插入排序)***"<<std::endl;
BinaryInsertSort(array,0,MAXSIZE-1);
display(array,MAXSIZE);
std::cout<<std::endl<<"***希尔排序(SHELL SORT)***"<<std::endl;
ShellSort(array,0,MAXSIZE);
display(array,MAXSIZE);
std::cout<<std::endl<<"***快速排序***"<<std::endl;
QuickSort(array,0,MAXSIZE);
display(array,MAXSIZE);
std::cout<<std::endl<<"***三路划分的快速排序***"<<std::endl;
Quick_Sort(array,0,MAXSIZE);
display(array,MAXSIZE);
std::cout<<std::endl<<"***直接选择排序***"<<std::endl;
SelectSort(array,0,MAXSIZE);
display(array,MAXSIZE);
std::cout<<std::endl<<"***堆排序***"<<std::endl;
HeapSort(array,MAXSIZE);
display(array,MAXSIZE);
return 0;
}
[/size][/size][/color]#include<iostream>
#include<ctime>
#define Swap(i,j) {int s = (i); (i) = (j); (j) = s;}
const int MAXSIZE = 30;
int array[MAXSIZE];
/*直接插入排序
基本思想:当插入第I个元素时,前面的V[0],V[1]....V[I-1]已经排好序,这时用V[I]的排序码与
V[I-1],V[I-2]....的排序码进行比较,找到插入位置即将V[I]插入,原来位置上的元素向后移.
*/
void InsertSort(int (&array)[MAXSIZE],const int left,int const right)
{
for (int i=left+1;i<=right;i++)
{
if (array[i] < array[i-1])
{
int temp = array[i], j = i-1;
do
{
array[j+1] = array[j]; j--;
}
while (j >= left && temp < array[j]);
array[j+1] = temp;
}
}
}
/*折半插入排序(二分法插入排序)
基本思想:设在数据表中有一个元素序列V[0],V[1]...V[n-1].其中V[0],V[1]...V[I-1]
是已经排好序的元素.在插入V[I]时,得用折半搜索寻找V[I]的插入位置.
*/
void BinaryInsertSort(int (&array)[MAXSIZE],int left,int right)
{
for (int i=left+1;i<=right;i++)
{
int temp = array[i];
while (left<=right)
{
int middle = (left+right)/2;
if (temp < array[i]) right = middle - 1;
else left = middle + 1;
}
for (int k=i-1;k>=left;k--) array[k+1] = array[k];
array[left] = temp;
}
}
/*希尔排序(SHELL SORT),又称缩小增量排序(diminishing-increment sort)
基本思想:设待排序元素序列有N个元素,首先取出一个整数gap<n作为间隔,将全部元素分为gap
个字序列,所有距离为gap的元素放在同一个子序列中,在每一个子序列中分别施行直接插入排序.
然后缩小间隔gap,直到gap等于 1
*/
void ShellSort(int (&array)[MAXSIZE],const int left,const int right)
{
int gap = right-left+1; //增量的初始值
do
{
gap = gap/3 + 1; // 求下一增量
for (int i=(left+gap);i<=right;i++) //各子充列交错处理
if (array[i] < array[i-gap]) //逆序
{
int temp = array[i], j = i-gap;
do
{
array[j+gap] = array[j]; //后移元素
j = j-gap; //现比较前一元素
}while (j>left &&temp < array[j]);
}
}while (gap > 1);
}
/*快速排序
快速排序采用分治法(divide-and-conquer)进行排序.
基本思想:任取待排序元素序列中某个元素作基准,按照该元素排序码大小,将整个元素序列划分为左右两个
子序列,左侧都比基准元素小,右侧则大于或等于.然后分别对这两个子序列重复施行上述方法,直到所有的元素
都排在相应位置为止
*/
//快速排序的划分
int Partition(const int left,const int right)
{
int pivotpos = left,pivot = array[left]; //基准元素
for (int i=left+1;i<=right;i++)
if (array[i] <pivot)
{
pivotpos++;
if (pivotpos != i) Swap(array[pivotpos],array[i]);
}
array[left] = array[pivotpos];
array[pivotpos] = pivot;
return pivotpos;
}
//快速排序
void QuickSort(int(&array)[MAXSIZE],const int left,const int right)
{
if (right-left <= 25) InsertSort(array,0,MAXSIZE-1); //数据规模较小时,采用直接插入.
else
{
int pivotpos = Partition(left,right);
QuickSort(array,left,pivotpos-1);
QuickSort(array,pivotpos+1,right);
}
}
//三路划分的快速排序算法
void Quick_Sort(int (&array)[MAXSIZE],int low,int high)
{
int pivot=array[low];
if (low >= high) return;
while (low<high)
{
while (low<high && pivot<array[high]) high--;
if (low<high)
{
array[low]=array[high];
low++;
}
while (low<high && pivot>=array[low]) low++;
if (low<high)
{
array[high]=array[low];
high++;
}
}
array[low]=pivot;
Quick_Sort(array,low,low-1);
Quick_Sort(array,low+1,high);
}
/*
选择排序
基本思想:每一趟(纺织品如第 I 趟,I = 0,1,2,...N-2)在后面 N-I个待排序元素中选出排序码
最小的元素,作为有序元素序列的第 I 个元素.待到第 N-2趟作完,待排序元素只剩下 1 个,就不用再选了.
*/
//直接选择排序
void SelectSort(int (&array)[MAXSIZE],const int left,const int right)
{
for (int i=left;i<right;i++)
{
int k = i;
for (int j=i+1;j<=right;j++)
if (array[j] < array[k]) k = j; //当前最小排序码的元素
if (k != i) Swap(array[i],array[k]);
}
}
/*
堆排序
(1):根据初始输入数据,得用堆的调整算法SiftDown()形成堆
(2):通过一系列的元素交换和重新调整堆进行排序
*/
//堆调整
void MaxHeap_SiftDown(int (&heap)[MAXSIZE],const int start,const int end)
{
int i=start,temp = heap[start], j = 2*start + 1;
while (j <= end) //检查是否到最后位置
{
if (j < end && heap[j] < heap[j+1]) j++;
if (temp >= heap[j]) break;
else //子女中大者上移
{
heap[i] = heap[j];
i = j; //i下降到子女位置
j = 2*j + 1;
}
}
heap[i] = temp; //将temp中元素放到适合位置
}
//堆排序
void HeapSort(int (&heap)[MAXSIZE],const int size)
{
for (int i=(size-2)/2;i>=0;i--)
MaxHeap_SiftDown(heap,i,size-i);
for (int j=size-1;j>=0;j--)
{
Swap(heap[0],heap[j]);
MaxHeap_SiftDown(heap,0,j-1);
}
}
//输出排序后的数列
void display(int (&array)[MAXSIZE],int size)
{
for (int i=0;i<size;i++)
{
std::cout<<array[i]<<" ";
if ((i+1)%10 == 0) std::cout<<std::endl;
}
}
int main(void)
{
srand(unsigned(time(NULL)));
for (int i=0;i<MAXSIZE;i++)
array[i] = rand()%10000;
std::cout<<"***直接插入排序***"<<std::endl;
InsertSort(array,0,MAXSIZE-1);
display(array,MAXSIZE);
std::cout<<std::endl<<"***折半插入排序(二分法插入排序)***"<<std::endl;
BinaryInsertSort(array,0,MAXSIZE-1);
display(array,MAXSIZE);
std::cout<<std::endl<<"***希尔排序(SHELL SORT)***"<<std::endl;
ShellSort(array,0,MAXSIZE);
display(array,MAXSIZE);
std::cout<<std::endl<<"***快速排序***"<<std::endl;
QuickSort(array,0,MAXSIZE);
display(array,MAXSIZE);
std::cout<<std::endl<<"***三路划分的快速排序***"<<std::endl;
Quick_Sort(array,0,MAXSIZE);
display(array,MAXSIZE);
std::cout<<std::endl<<"***直接选择排序***"<<std::endl;
SelectSort(array,0,MAXSIZE);
display(array,MAXSIZE);
std::cout<<std::endl<<"***堆排序***"<<std::endl;
HeapSort(array,MAXSIZE);
display(array,MAXSIZE);
return 0;
}
[[it] 本帖最后由 zjl138 于 2008-7-21 21:27 编辑 [/it]]
