基于C++实现的各种内部排序算法汇总

提起排序算法相信大家都不陌生，或许很多人已经把它们记得滚瓜烂熟，甚至随时可以写出来。是的，这些都是最基本的算法。这里就把各种内部排序算法总结归纳了一下，包括插入排序（直接插入排序，折半插入排序，希尔排序）、交换排序（冒泡排序，快速排序）、选择排序（简单选择排序，堆排序）、2-路归并排序。（另：至于堆排序算法，前面已经有一篇文章针对堆排序的算法实现做了详细的描述）

C++实现代码如下：

#include
using namespace std;

typedef int ElementType;


void InsertSort(ElementType A[], int n)
{
 int i,j;
 ElementType temp; // 临时变量

 for(i=1; i0 && A[j-1]>temp; --j)
 A[j] = A[j-1];
 A[j] = temp;
 }
}


void BinaryInsertSort(ElementType A[], int n)
{
 int i, j, low, high, mid;
 ElementType temp;
 for(i=1; i temp)
 high = mid-1;
 else
 low = mid+1;
 }

 for(j=i-1; j>=high+1; --j) // 统一后移
 A[j+1] = A[j];
 A[high+1] = temp; // 插入
 }
}


void ShellSort(ElementType A[], int n)
{
 int i, j, dk; // dk是增量
 ElementType temp;
 
 for(dk=n/2; dk>0; dk/=2) // 增量变化
 {
 for(i=dk; i=0 && A[j]>temp; j-=dk)
 A[j+dk] = A[j]; // 后移
 A[j+dk] = temp;
 }
 }
}


void BubbleSort(ElementType A[], int n)
{
 for(int i=0; ii; --j) // 从后往前
 {
 if(A[j-1] > A[j]) 
 {
 flag = true;
 // 交换
 A[j-1] = A[j-1]^A[j];
 A[j] = A[j-1]^A[j];
 A[j-1] = A[j-1]^A[j];
 }
 }

 if(flag == false)
 return;
 }
}


int Partition(ElementType A[], int low, int high)
{
 // 划分操作有很多版本，这里就总以当前表中第一个元素作为枢纽/基准
 ElementType pivot = A[low];
 while(low < high)
 {
 while(low=pivot)
 --high;
 A[low] = A[high]; // 将比枢纽值小的元素移到左端
 while(lowA[largest])
 ++largest;   // 如果右子结点大
 if(temp < A[largest])
 {
 A[i] = A[largest];
 i = largest;   // 记录交换后的位置
 }
 else
 break;
 }
 A[i] = temp; // 被筛选结点的值放入最终位置
}
void BuildMaxHeap(ElementType A[], int len)
{
 for(int i=len/2-1; i>=0; --i) // 从i=[n/2]~1，反复调整堆
 AdjustDown(A, i, len);
}
void HeapSort(ElementType A[], int n)
{
 BuildMaxHeap(A, n);  // 初始建堆
 for(int i=n-1; i>0; --i) // n-1趟的交换和建堆过程 
 {
 // 输出最大的堆顶元素（和堆底元素交换）
 A[0] = A[0]^A[i];
 A[i] = A[0]^A[i];
 A[0] = A[0]^A[i];
 // 调整，把剩余的n-1个元素整理成堆
 AdjustDown(A, 0, i); 
 }
}


ElementType *B = new ElementType[13]; // 和数组A一样大
void Merge(ElementType A[], int low, int mid, int high)
{
 int i, j, k;
 for(k=low; k<=high; ++k)
 B[k] = A[k];    // 将A中所有元素复制到B
 for(i=low,j=mid+1,k=i; i<=mid&&j<=high; ++k)
 {
 if(B[i] <= B[j])  // 比较B的左右两段序列中的元素
 A[k] = B[i++]; // 将较小值复制到A中
 else
 A[k] = B[j++];
 }
 while(i<=mid) A[k++] = B[i++]; // 若第一个表未检测完，复制
 while(j<=high) A[k++] = B[j++]; // 若第二个表未检测完，复制
}

void MergeSort(ElementType A[], int low, int high)
{
 if(low < high)
 {
 int mid = (low + high)/2;
 MergeSort(A, low, mid);  // 对左侧子序列进行递归排序
 MergeSort(A, mid+1, high); // 对右侧子序列进行递归排序
 Merge(A, low, mid, high);  // 归并
 }
}


void print(ElementType A[], int n)
{
 for(int i=0; i

相信本文所述实例代码对大家复习和巩固各类排序算法能起到一定的帮助作用。