基于模板类的排序算法(快速排序,插入排序)

2016-11-23

版权声明:本文为作者原创文章,可以随意转载,但必须在明确位置表明出处!!!

快速排序

  • 算法的基本思想:

    把每一趟排序结果分为两部分,其中一部分的没每个值都要比另外一部分的值小,然后再按照此种方法把分成的两部分在进行相同的排序直到待排序的序列不能分为两部分为止,整个排序过程可以递归进行
  • 算法原理

  1. 设定变量nFirst,nLast,nFirst指向待排序的第一个下标索引,nLast指向待排序的最后一个索引
  2. 设定一个元素作为分成两部分的关键元素key,key=array[0];
  3. 从nLast往nFirst方向搜索,依次与key比较,若array[nLast] <= key,则把array[nLast]和array[nFirst]互换
  4. 从nFirst方向向nLast方向索搜,一次与与key比较,若array[nFirst] > key,则把array[nFirst]和array[nLast]互换
  5. 重复第三,第四部,因第三部由后往前找nLast–,第四步由前往后找nFirst++,当nFirst == nLast则表示一趟排序完成
  6. 把比key值小的部分和比key值大的部分再次通过1,2,3,4,5,6步执行直到所有待排序列不能分为两部分为止
  • 时间复杂度:

    最坏时间复杂度为O(n^2),最好时间复杂度为O(nlog2n),平均复杂度为O(nlog2n)

  • 稳定性:

    快速排序是不稳定排序

算法实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
template<class T>
void Algorithm<T>::quickSort(T *array, std::size_t nLow, std::size_t nHigh, int (*fCompare)(const T *, const T *))
{
if(0 == *array || nLow >= nHigh) return ;
int nFirst = nLow;
int nLast = nHigh;
T nKey = array[nFirst];//设定一个key值用来划分数据,比key值小的在它的左边,比它大的在它右边
while(nFirst < nLast)
{
//从右边开始找比key值小的数,如果比key值大则下标向左移
while(nFirst < nLast && fCompare(&nKey, &array[nLast]) <= 0)
{
-- nLast;
}
//把比key值小的元素赋值给数组的一个元素
array[nFirst] = array[nLast];
//从左边开始找比key大的数,如果比key值小则下标向右移动
while(nFirst < nLast && fCompare(&nKey, &array[nFirst]) >= 0)
{
++ nFirst;
}
//把比key值打的元素赋值给最后一个元素
array[nLast] = array[nFirst];
}
array[nFirst] = nKey;
quickSort(array, nLow, nFirst - 1, fCompare);//对小于key的左边区域再排序
quickSort(array, nFirst + 1, nHigh, fCompare);//对大于key的区域再排序
}

插入排序

  • 算法的基本思想:

    每次将一个待排序的元素插入到已经排序好的数据集合中,使得到新的数据集合任然有序

  • 算法原理

  1. 设置监视哨array[0],这个时候array[0]就作为一个已经排好序的序列了。
  2. 从array[0]向后搜索,若比array[0]小,则将array[1]插入到array[0]前面
  3. 这个时候第一个元素和第二个元素作为有序序列了,然后第三个元素和分别和前面两个元素比较,并插入到响应位置
  4. 重复1,2,3步骤知道所有数据插入完成
  • 时间复杂度:

    最好情况时间复杂度O(n),最坏时间复杂度O(n^2)。

  • 稳定性:

    插入排序是稳定排序算法

算法实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
template<class T>
void Algorithm<T>::insertSort(T *array, std::size_t nLength, int (*fCompare)(const T*, const T*))
{
if(0 == *array || nLength <= 0) return;
T temp;
int index = 0;
for(int nLoop = 1; nLoop < nLength; nLoop ++)
{
temp = array[nLoop];
for(index = nLoop; index > 0 && fCompare(&array[index - 1], &temp) > 0; index --)
{
array[index] = array[index -1];
}
array[index] = temp;
}
}

折半插入排序

  • 算法的基本思想

    折半插入是直接插入的改进,因为直接插入排序是让待排序的元素依次和已排序好的元素比较,这样比较的次数比较多,折半插入是把已排好序的元素一份为二,若待排元素比中间元素小则在前半段再按二分查找,若比中间元素大则在后半段再次按照二分查找知道找到位置,这样就大大减少了比较的次数了。

  • 算法原理

  1. 把第一个元素作为nLow,第二个元素作为待排序的元素,下标为nHigh
  2. nMid元素为(nLow+nHigh-1)/2。
  3. 比较待排元素和nMid元素的大小,若小于nMid,则nHigh = nMid - 1,反之nLow = nMid + 1。
  4. 若找到插入的位置,则这个时候的插入位置为nLow,然后依次移动响应位置后插入待排序元素
  • 算法时间复杂度

    折半插入只是减少了比较的次数,并没有减少元素移动的次数,所有算法的时间复杂度任然为O(n^2)。

  • 稳定性

    折半插入是稳定排序算法

算法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
template<class T>
void Algorithm<T>::binaryInsertSort(T *array, std::size_t nLength, int (*fCompare)(const T*, const T*))
{
if(0 == *array || nLength <= 0) return;
for(int nLoop = 1; nLoop < nLength; nLoop ++)
{
T temp = array[nLoop];
int nLow = 0;
int nHigh = nLoop - 1;
while(nLow <= nHigh)
{
int nMid = (nLow + nHigh) / 2;
if(fCompare(&temp, &array[nMid]) > 0)
{
nLow = nMid + 1;
}
else
{
nHigh = nMid - 1;
}
}
for(int index = nLoop; index > nLow; index --)
{
array[index] = array[index - 1];
}
array[nLow] = temp;
}
}

项目文件地址:https://github.com/Gavinxyj/Algorithm


推荐我的微信公众号:爱做饭的老谢


上一篇:基于模板类的排序算法(冒泡排序,选择排序)
下一篇:基于模板类的排序算法(希尔排序,归并排序)