各种排序算法的c++代码实现

下面是c++实现选择排序、冒泡排序、插入排序、基数排序、快速排序、归并排序的代码，能够显示各种排序算法的中间过程。

#include <iostream>
#include <string.h>
#include <windows.h>
using namespace std;
//下面的函数是交换大小

void swap(int &x, int &y)
{
int temp = x;
 x = y;
 y = temp;
}
//下面的函数用来寻找最大元素所在的位置

template<class T>
int indexOfMax(T a[], int n)
{
int max = 0;
for (int i = 1; i < n; i++)
 {
if (a[max] < a[i])
 max = i;
 }
return max;
}

//下面是选择排序算法
template<class T>
void selectionSort(T a[], int n)
{
for (int size = n; size >1; size--)
 {
int j = indexOfMax(a, size);
//int temp = a[j];
//a[j] = a[size - 1];
//a[size - 1] =temp;
 swap(a[j], a[size - 1]);
for (int i = 0; i < n; i++)
 {
cout<<a[i]<<endl;
 }
cout << "\n";
 }
}

//下面是冒泡排序
template <class T>
void bubbleSort(T a[], int n)
{
for (int i = n; i > 1; i--)
 {
//下面是一次冒泡的过程，实现的是将a[0:i-1]的最大值冒泡的最右端
for (int j = 0; j < i - 1; j++)
 {
if (a[j] > a[j + 1])
 swap(a[j], a[j + 1]);
 }
for (int i = 0; i < n; i++)
 {
cout<<a[i]<<endl;
 }
cout << "\n";
 }
}

//下面是插入排序
template <class T>
void insertionSort(T a[], int n)
{
for (int i = 1; i < n; i++)
 {
//下面将a[i]插入到a[0:i-1]中去
int temp = a[i];
int j;
for (j=i-1;j>=0 && a[j]>temp; j--)
 {
 a[j+1] = a[j];
 }
 a[j+1] = temp;

for (int i = 0; i < n; i++)
 {
cout<<a[i]<<endl;
 }
cout << "\n";

 }
}
//下面是计数排序
template <class T>
void countSort(T a[], T b[], T result[],int n)
{
int *c= new int[10];
for (int i = 0; i <10; i++) {
 c[i] = 0;
 }
for (int i = 0; i < n; i++) {
 c[b[i]] += 1;
 }
for (int i = 0; i <10; i++) {
if (i != 0) {
 c[i] += c[i - 1];
 }
 }
for (int i = n - 1; i >= 0; i--) {
// 和计数排序唯一的差别在于赋值的时候用真实的数据 
 result[c[b[i]] - 1] = a[i];
 c[b[i]] = c[b[i]] - 1;
 }
}


//下面是基数排序
template <class T>
void radixSort(T a[], int maxLen,int n) 
{
int *result = new int[n];
int flag = 1;
int *b= new int[n];//用来储存某一位各个数的值
for(int i = 0;i < maxLen; i++ )
 {
 flag *= 10;
//将每个a里的数的对应数值储存到b里
for (int j = 0; j <n; j++)
 {
 b[j] = a[j] % flag;
 b[j] = b[j] / (flag / 10);
 }
//下面调用计数排序
 countSort(a, b, result,n);
// 每一轮计数排序完后刷新下一轮要排序的数组 
for (int j = 0; j < n; j++)
 {
 a[j] = result[j];
 }
for (int j = 0; j <n; j++)
 {
cout<<a[j]<<endl;

 }
cout << "\n";
 }
}

//下面是快速排序
void quick_sort(int array[],int first, int last)
{
int temp, low, high, list_separator;

 low = first;
 high = last;
 list_separator = array[(first + last)/2];

do 
 {
while (array[low] < list_separator) {
 low++;
 }
while (array[high] > list_separator) {
 high--;
 }
if (low <= high) {
 temp = array[low];
array[low++] = array[high];
array[high--] = temp;
 }
 } while (low <= high);

if (first < high) {
 quick_sort(array, first, high);
 }
if (low < last) {
 quick_sort(array, low, last);
 }
}

//下面是归并排序
void merge(int array[],int left,int mid,int right) 
{ 
int len = right - left + 1; 
int *t = new int[len]; 
int i = left,j = mid + 1; 
int k = 0;//t数组下标 
while(i <= mid && j <= right) 
 { 
if(array[i] < array[j]) 
 { 
 t[k++] = array[i++];//直接把++放下标里面方便啊 
 } 
else 
 { 
 t[k++] = array[j++]; 
 } 
 } 
while(i <= mid)//表示前面的那段还没全部被抽取 
 { 
 t[k++] = array[i++]; 
 } 
while(j <= mid)//表示后面的那段还没全部被抽取 
 { 
 t[k++] = array[j++]; 
 } 

//把t反馈回array的left~right段 
for(k = 0;k < len;k++) 
 { 
array[left++] = t[k]; 
 } 

delete []t;//记得回收临时空间 
} 

//递归大法 
void merge_sort(int array[],int left,int right) 
{ 
if(left < right)//如果left>=right表明细分成最小的一个元素一组 
 { 
int mid = (left + right) / 2; //中间 
//注意这里递归之后right变量已经被赋值为mid 
 merge_sort(array,left,mid); 
//注意这里递归之后left变量已经被赋值为mid 
 merge_sort(array,mid+1,right); 
//合并得到有序序列 
 merge(array,left,mid,right); 
 } 
} 

void print(int *array,int start,int end) 
{ 
while(start < end) 
 { 
cout<<array[start]<<" "; 
 start++; 
 } 
cout<<array[end]<<endl; 
} 


int main()
{
//选择排序
// int a[] = {5,4,3,2,1};
// selectionSort(a,5);
// system("pause");

//冒泡排序
// int a[] = {5,4,3,2,1};
// bubbleSort(a,5);
// system("pause");

//插入排序
// int a[] = {5,4,3,2,1};
// insertionSort(a,5);
// system("pause");

//冒泡排序
// int a[] = {5,4,3,2,1};
// bubbleSort(a,5);
// system("pause");

//基数排序
// int a[] = {55,433,32,28,1};
// radixSort(a,5,5);
// system("pause");

//快排
// int values[30], i;
// for (i = 0; i < 30; i++) {
// values[i] = rand();
// }

// cout << "Before the quick_sort:" << endl;
// for (i = 0; i < 30; i++) {
// cout << values[i] << endl;
// }
// cout << "\n\n";

// quick_sort(values,0,29);

// cout << "After the quick_sort:" << endl;
// for (i = 0; i < 30; i++) {
// cout << values[i] << endl;
// }



int values[30], i;
for (i = 0; i < 30; i++) {
 values[i] = rand();
 }
cout << "Before the quick_sort:" << endl;
for (i = 0; i < 30; i++) {
cout << values[i] << endl;
 }
cout << "\n\n";

 merge_sort(values,0,30);

cout << "After the quick_sort:" << endl;
for (i = 0; i < 30; i++) {
cout << values[i] << endl;
 }









return 0;
}