C++八大排序算法(2)

要点：建堆、交换、调整堆 实现：

Void HeapSort(Node L[]) {

BuildingHeap(L);//建堆（大根堆） For(int i=n;i>0;i--)//交换 {

Int temp=L[i]; L[i]=L[0]; L[0]=temp;

Heapify(L,0,i);//调整堆 } }

Void BuildingHeap(Node L[]) { For(i=length/2 -1;i>0;i--)

Heapify(L,i,length); }

归并排序

原理：将原序列划分为有序的两个序列，然后利用归并算法进行合并，合并之后即为有序序列。

要点：归并、分治 实现：

Void MergeSort(Node L[],int m,int n) {

Int k; If(m

K=(m+n)/2; MergeSort(L,m,k); MergeSort(L,k+1,n); Merge(L,m,k,n); } }

基数排序

原理：将数字按位数划分出n个关键字，每次针对一个关键字进行排序，然后针对排序后的序列进行下一个关键字的排序，循环至所有关键字都使用过则排序完成。

要点：对关键字的选取，元素分配收集。 实现：

Void RadixSort(Node L[],length,maxradix) {

Int m,n,k,lsp; k=1;m=1;

Int temp[10][length-1]; Empty(temp); //清空临时空间

While(k

For(int i=0;i

If(L[i]

Temp[0][n]=L[i]; Else

Lsp=(L[i]/m); //确定关键字 Temp[lsp][n]=L[i]; n++; }

CollectElement(L,Temp); //收集 n=0; m=m*10; k++; } }

C语言指针实现排序算法［转载］

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的数，前面没有任何数，单单一个，认为