编程中排序的几种方法

74 阅读 0 评论 49 点赞

我是靠谱客的博主独特摩托，最近开发中收集的这篇文章主要介绍编程中排序的几种方法，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

（1）插入排序

分析：　插入排序就是通过数字插入有序数组的方式进行排序的，代码简单，且易理解。时间复杂度O(N*N)
代码如下：

template <typename T>
void InsertSort(vector<T>& array)
{
for(int i=0; i<array.size(); ++ i)
{
for(int j=i; j>0; -- j)
{
if(array[j] < array[j-1])
swap(array[j], array[j-1]);
else
break;
}
}
}

（2）冒泡排序

分析：冒泡排序多次遍历数组，每次遍历将当前位置与后面位置的数进行比较，大的放后面，这样每次遍历最后一位数字必为整个数组中最大的元素，经过n-1次遍历后，整个数组有序。时间复杂度O(N*N)
代码如下：

template <typename T>
void BubbleSort(vector<T>& array)
{
for(int i=array.size()-1; i>0; -- i)
{
for(int j=0; j<i; ++ j)
{
if(array[j] > array[j+1])
swap(array[j], array[j+1]);
}
}
}

（3）归并排序

分析：两个有序数组的合并，应该都很熟悉。现在将一个数组N个元素，将它看做N个数组，每个数组一个元素，这样任意一个数组都是有序的，然后两两合并（有序数组的合并），会得到N/2个有序数组，然后在两两合并… ，直到数组数量为1，即为归并排序。时间复杂度O(N*log(N))
代码如下：

template <typename T>
void Merge(vector<T> &array, vector<T> &res, int b, int e)
{
if(b < e)
{
int mid = (b + e) >> 1;
Merge(array, res, b, mid);
Merge(array, res, mid+1, e);
int i = b, j = mid + 1;
int k = b;
while(i <= mid && j <= e)
{
if(array[i] < array[j])
res[k ++] = array[i ++];
else
res[k ++] = array[j ++];
}
while(i <= mid)
res[k ++] = array[i ++];
while(j <= e)
res[k ++] = array[j ++];
for( ; b <= e; ++ b)
array[b] = res[b];
}
}
template <typename T>
void MergeSort(vector<T> &array)
{
vector<int> tmp(array.size());
Merge(array, tmp, 0, array.size()-1);
}

（4）快速排序

分析：最常用的算法就是快速排序，既然常用就有必要知道它的排序原理了。
首先从数组中选择一个数字X（最好是数组中的中位数，原因往下看），然后用首尾指针将大于X的放在数组的右边，小于X的放在数组左边，这样在X的左边的数字全部为小于X的数字，在X右边的数字全部为大于X的数字。对于数字X，它的位置已经确定；然后将X左边和X右边依次递归进行这样的过程，最后得到的数字即为有序。
选取数组中的中位数（实际上采用三数中值分割的方法），会将递归的层数减少(每次少一半，)，使复杂度趋近Nlog(N);
如果每次选取的数字为待排序部分中，最小或最大的，会加大递归层数(每次少1), 复杂度趋近 NN
代码如下：

//从首尾中，三个数字中，选取中间的数字作为数字X
template <typename
T>
T getMid(int b, int e, vector<T> &array)
{
int mid = (b + e) >> 1;
if(array[b] > array[mid])
swap(array[b], array[mid]);
if(array[b] > array[e])
swap(array[b], array[e]);
if(array[mid] > array[e])
swap(array[mid], array[e]);
swap(array[mid], array[e]);
return array[e];
}
template <typename
T>
void InsertSort(vector<T> &array, int b, int e)
{
for(int i=b; i<e; ++ i)
{
for(int j = i; j > b; -- j)
{
if(array[j] < array[j-1])
swap(array[j], array[j-1]);
else
break;
}
}
}
template <typename
T>
void Qsort(vector<T> &array, int b, int e)
{
if(b + 3 > e)
{
T mid = getMid(b ,e, array);
int i = b, j = e;
for(;;)
{
while(array[++ i] <= mid);
while(array[-- j] > mid);
if(i < j)
swap(array[i], array[j]);
else
break;
}
swap(array[i], array[e]);
Qsort(array, b, i-1);
Qsort(array, i+1, e);
}
else
InsertSort(array, b, e);
}
template <typename
T>
void QuickSort(vector<T> &array)
{
Qsort(array, 0, array.size()-1);
}