/*-----------各种排序算法总结----------*/
*****************************************************************/
/*-----------(1)直接插入排序算法-------------*/
/*--------------------------------------------------------------
直接插入排序(Insertion Sort)的基本思想是:每次将一个待排序的记录,
按其关键字大小,从后向前扫描插入到前面已经排好序的子序列中的适当
位置,直到全部记录插入完成为止。
设数组为a[0…n-1]。
1.初始时,a[0]自成1个有序区,无序区为a[1..n-1]。令i=1
2.将a[i]并入当前的有序区a[0…i-1]中形成a[0…i]的有序区间。
3.i++并重复第二步直到i==n-1。排序完成。
---------------------------------------------------------------*/
/*-----------------------由小到大直接排序------- --------------
void Insertsort1(int a[], int n)
{
int i, j;
for (i = 1; i < n; i++)//外层循环表示待比较的数值
for (j = i - 1; j >= 0; j--)//内层循环搜索待插入位置,从后向前扫描
{
if(a[j] > a[j + 1])
Swap(a[j], a[j + 1]);
}
}
/*----------------------改进后的直接排序----------------------*/
void Insertsort2(int a[], int n)
{
int i, j;
for (i = 1; i < n; i++)
for (j = i - 1; j >= 0 && a[j] > a[j + 1]; j--)
Swap(a[j], a[j + 1]);
}
--------------------------------------------------------------*/
/***************************************************************/
/*-----------(2)希尔排序算法-------------*/
/*--------------------------------------------------------------
希尔排序的实质就是分组插入排序,该方法又称缩小增量排序。
该方法的基本思想是:先将整个待排元素序列分割成若干个子序列(由相隔
某个“增量”的元素组成的)分别进行直接插入排序,然后依次缩减增量再进
行排序,...,最后增量为1,再对全体元素进行一次直接插入排序。
一般,希尔排序的增量选择都是从n/2开始,每次再减半,直到增量为1。
---------------------------------------------------------------*/
/*-----------------------由小到大希尔排序------- --------------
void shellsort(int a[], int n)
{
int i, j, gap;
for (gap = ( n + 1 ) / 2; gap > 0; gap = ( gap + 1 ) / 2)//gap为增量
for (i = gap; i < n; i++)
for (j = i - gap; j >= 0 && a[j] > a[j + gap]; j -= gap)
Swap(a[j], a[j + gap]);
}
--------------------------------------------------------------*/
/***************************************************************/
/*-----------(3)冒泡排序算法-------------*/
/*--------------------------------------------------------------
冒泡排序基本思想是:(以升序为例)含有n个元素的数组原则上要进行n-1
次排序。对于每一次的排序,从第一个数开始,依次比较前一个数与后一个
数的大小。如果前一个数比后一个数大,则进行交换。这样一轮过后,最大
的数将会出现称为最末位的数组元素。第二轮则去掉最后一个数,对前n-1个
数再按照上面的步骤找出最大数,该数将称为倒数第二的数组元素...n-1轮
过后,就完成了排序。
---------------------------------------------------------------*/
/*-----------------------由小到大冒泡排序------- --------------
void BubbleSort(int a[], int n)
{
int i, j;
for (i = 0; i < n-1; i++)//外层循环控制循环次数
for (j = 0; j < n-1-i; j ++)//内层循环选择待比较的数
{
if(a[j] > a[j+1])
Swap(a[j], a[j + 1]);
}
}
--------------------------------------------------------------*/
/***************************************************************/
/*-----------(4)快速排序算法-------------*/
/*--------------------------------------------------------------
快速排序是一种划分交换排序。它采用了一种分治的策略。
该方法的基本思想是:
1.先从数列中取出一个数作为基准数。
2.分区过程,将比这个数大的数全放到它的右边,小于或等于它的数全放到它的左边。
3.再对左右区间重复第二步,直到各区间只有一个数。
对挖坑填数+分治法进行总结
1.i =left; j = right; 将基准数挖出形成第一个坑a[i]。
2.j--由后向前找比它小的数,找到后挖出此数填前一个坑a[i]中。
3.i++由前向后找比它大的数,找到后也挖出此数填到前一个坑a[j]中。
4.再重复执行2,3二步,直到i==j,将基准数填入a[i]中。
---------------------------------------------------------------*/
/*-----------------------由小到大快速排序------- --------------
void quick_sort(int a[], int left, int right)
{
if (left < right)
{
//Swap(a[left], a[(left + right) / 2]);
//有的书上是以中间的数作为基准数的,直接将中间的这个数和第一个数交换
int i = left, j = right, x = a[left];
while (i < j)
{
while(i < j && a[j] >= x) // 从右向左找第一个小于x的数
j--;
if(i < j)
a[i++] = a[j];
while(i < j && a[i] < x) // 从左向右找第一个大于等于x的数
i++;
if(i < j)
a[j--] = a[i];
}
a[i] = x;
quick_sort(a, left, i - 1); // 递归调用
quick_sort(a, i + 1, right);
}
}
--------------------------------------------------------------*/
/***************************************************************/
/*-----------(5)直接选择排序算法-------------*/
/*--------------------------------------------------------------
直接选择排序的基本思想是:第一次从R[0]~R[n-1]中选取最小值,与R[0]交换,
第二次从R[1]~R[n-1]中选取最小值,与R[1]交换,...,第i次从R[i-1]~R[n-1]
中选取最小值,与R[i-1]交换,....,第n-1次从R[n-2]~R[n-1]中选取最小值,
与R[n-2]交换,总共通过n-1次,得到一个有序序列。
---------------------------------------------------------------*/
/*-----------------------由小到大直接选择排序------- --------------
void select_sort(int a[], int n)
{
int i,j,min_pos;
for(i = 0; i < n-1; i++)
{
min_pos = i;
for(j = i+1; j < n; j++)
{
if(a[j] < a[min_pos])
{
min_pos = j;//记录最小元素的下标
}
}
if(min_pos != i)
swap(a[i],a[min_pos]);
}
}
--------------------------------------------------------------*/
/***************************************************************/
/*-----------(6)堆排序算法-------------*/
/*--------------------------------------------------------------
堆排序的基本思想是:。
---------------------------------------------------------------*/
/*-----------------------由小到大堆排序------- --------------
template<typename T>
void MinHeapify(T *arry,int size,int element)
{
int lchild=element*2+1,rchild=lchild+1;//左右子树
while(rchild < size)//子树均在范围内
{
if(arry[element]<=arry[lchild]&&arry[element]<=arry[rchild])//如果比左右子树都小,完成整理
{
return;
}
if(arry[lchild]<=arry[rchild])//如果左边最小
{
swap(arry[element],arry[lchild]);//把左面的提到上面
element=lchild;//循环时整理子树
}
else//否则右面最小
{
swap(arry[element],arry[rchild]);//同理
element=rchild;
}
lchild=element*2+1;
rchild=lchild+1;//重新计算子树位置
}
if(lchild<size&&arry[lchild]<arry[element])//只有左子树且子树小于自己
{
swap(arry[lchild],arry[element]);
}
return;
}
template<typenameT>
void HeapSort(T *arry,int size)
{
int i;
for(i=size-1;i>=0;i--)//从子树开始整理树
{
MinHeapify(arry,size,i);
}
while(size>0)//拆除树
{
swap(arry[size-1],arry[0]);//将根(最小)与数组最末交换
size--;//树大小减小
MinHeapify(arry,size,0);//整理树
}
return;
}
--------------------------------------------------------------*/
/***************************************************************/
/*-----------(7)归并排序算法-------------*/
/*--------------------------------------------------------------
归并排序是建立在归并操作上的一种有效的排序算法。
归并操作的过程如下:
1.申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列
2.设定两个指针,最初位置分别为两个已经排序序列的起始位置
3.比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置
4.重复步骤3直到某一指针达到序列尾
5.将另一序列剩下的所有元素直接复制到合并序列尾
---------------------------------------------------------------*/
/*-----------------------由小到大归并排序------- --------------
//将有二个有序数列a[first...mid]和a[mid+1...last]合并。
void mergearray(int a[], int first, int mid, int last, int temp[])
{
int i = first, j = mid + 1;
int m = mid, n = last;
int k = 0;
while (i <= m && j <= n)
{
if (a[i] <= a[j])
temp[k++]