C++实现八个常用的排序算法插入排序、冒泡排序、选择排序、希尔排序等

/* 
* 实现了八个常用的排序算法：插入排序、冒泡排序、选择排序、希尔排序 
* 以及快速排序、归并排序、堆排序和LST基数排序 
* @author gkh178 
*/ 
#include  
 
template 
void swap_value(T &a, T &b) 
{ 
 T temp = a; 
 a = b; 
 b = temp; 
} 
 
//插入排序：时间复杂度o(n^2) 
template 
void insert_sort(T a[], int n) 
{ 
 for (int i = 1; i = 0 && a[j] > temp) 
 { 
 a[j + 1] = a[j]; 
 --j; 
 } 
 a[j + 1] = temp; 
 } 
} 
 
//冒泡排序：时间复杂度o(n^2) 
template 
void bubble_sort(T a[], int n) 
{ 
 for (int i = n - 1; i > 0; --i) 
 { 
 for (int j = 0; j  a[j + 1]) 
 { 
 swap_value(a[j], a[j + 1]); 
 } 
 } 
 } 
} 
 
//选择排序：时间复杂度o(n^2) 
template 
void select_sort(T a[], int n) 
{ 
 for (int i = 0; i  
void shell_sort(T a[], int n) 
{ 
 for (int gap = n / 2; gap >= 1; gap /= 2) 
 { 
 for (int i = gap; i = 0 && a[j] > temp) 
 { 
 a[j + gap] = a[j]; 
 j -= gap; 
 } 
 a[j + gap] = temp; 
 } 
 } 
} 
 
//快速排序：时间复杂度o(nlgn) 
template 
void quick_sort(T a[], int n) 
{ 
 _quick_sort(a, 0, n - 1); 
} 
template 
void _quick_sort(T a[], int left, int right) 
{ 
 if (left  
int _partition(T a[], int left, int right) 
{ 
 T pivot = a[left]; 
 while (left = pivot) 
 { 
 --right; 
 } 
 a[left] = a[right]; 
 while (left  
void merge_sort(T a[], int n) 
{ 
 _merge_sort(a, 0, n - 1); 
} 
template 
void _merge_sort(T a[], int left, int right) 
{ 
 if (left  
void _merge(T a[], int left, int mid, int right) 
{ 
 int length = right - left + 1; 
 T *newA = new T[length]; 
 for (int i = 0, j = left; i <= length - 1; ++i, ++j) 
 { 
 *(newA + i) = a[j]; 
 } 
 int i = 0; 
 int j = mid - left + 1; 
 int k = left; 
 for (; i <= mid - left && j <= length - 1; ++k) 
 { 
 if (*(newA + i) <*(newA + j)) 
 { 
 a[k] = *(newA + i); 
 ++i; 
 } 
 else 
 { 
 a[k] = *(newA + j); 
 ++j; 
 } 
 } 
 while (i <= mid - left) 
 { 
 a[k++] = *(newA + i); 
 ++i; 
 } 
 while (j <= right - left) 
 { 
 a[k++] = *(newA + j); 
 ++j; 
 } 
 delete newA; 
} 
 
//堆排序：时间复杂度o(nlgn) 
template 
void heap_sort(T a[], int n) 
{ 
 built_max_heap(a, n);//建立初始大根堆 
 //交换首尾元素，并对交换后排除尾元素的数组进行一次上调整 
 for (int i = n - 1; i >= 1; --i) 
 { 
 swap_value(a[0], a[i]); 
 up_adjust(a, i); 
 } 
} 
//建立一个长度为n的大根堆 
template 
void built_max_heap(T a[], int n) 
{ 
 up_adjust(a, n); 
} 
//对长度为n的数组进行一次上调整 
template 
void up_adjust(T a[], int n) 
{ 
 //对每个带有子女节点的元素遍历处理，从后到根节点位置 
 for (int i = n / 2; i >= 1; --i) 
 { 
 adjust_node(a, n, i); 
 } 
} 
//调整序号为i的节点的值 
template 
void adjust_node(T a[], int n, int i) 
{ 
 //节点有左右孩子 
 if (2 * i + 1 <= n) 
 { 
 //右孩子的值大于节点的值，交换它们 
 if (a[2 * i] > a[i - 1]) 
 { 
 swap_value(a[2 * i], a[i - 1]); 
 } 
 //左孩子的值大于节点的值，交换它们 
 if (a[2 * i - 1] > a[i - 1]) 
 { 
 swap_value(a[2 * i - 1], a[i - 1]); 
 } 
 //对节点的左右孩子的根节点进行调整 
 adjust_node(a, n, 2 * i); 
 adjust_node(a, n, 2 * i + 1); 
 } 
 //节点只有左孩子，为最后一个有左右孩子的节点 
 else if (2 * i == n) 
 { 
 //左孩子的值大于节点的值，交换它们 
 if (a[2 * i - 1] > a[i - 1]) 
 { 
 swap_value(a[2 * i - 1], a[i - 1]); 
 } 
 } 
} 
 
//基数排序的时间复杂度为o(distance(n+radix)),distance为位数，n为数组个数，radix为基数 
//本方法是用LST方法进行基数排序，MST方法不包含在内 
//其中参数radix为基数，一般为10；distance表示待排序的数组的数字最长的位数；n为数组的长度 
template 
void lst_radix_sort(T a[], int n, int radix, int distance) 
{ 
 T* newA = new T[n];//用于暂存数组 
 int* count = new int[radix];//用于计数排序，保存的是当前位的值为0 到 radix-1的元素出现的的个数 
 int divide = 1; 
 //从倒数第一位处理到第一位 
 for (int i = 0; i = 0; --j) 
 { 
 int radixKey = (*(newA + j) / divide) % radix; 
 a[*(count + radixKey) - 1] = newA[j]; 
 --(*(count + radixKey)); 
 } 
 divide = divide * radix; 
 } 
} 

#include "Sort.h" 
using namespace std; 
 
template 
void printArray(T a[], int n) 
{ 
 for (int i = 0; i