排序算法模板实现示例分享
#include <cstdlib>
#include <iostream>
using namespace std;
#define SELECTSORT 1
#define INSERTSORT 1
#define BUBBLESORT 1
#define SHELLSORT 1
#define QUICKSORT 1
#define MERGESORT 1
template<typename T>
void print(T array[], int len)
{
for (int i=0; i<len; i++) {
cout<<array[i]<<" ";
}
cout<<endl;
}
template<typename T>
void Swap(T& a, T& b)
{
T temp = a;
a = b;
b = temp;
}
#ifdef SELECTSORT
template<typename T>
void SelectSort(T array[], int len)
{
int i = 0;
int j = 0;
int k = -1;
for (i=0; i<len; i++) {
k = i;
for (j=i+1; j<len; j++) {
if (array[j] < array[k]) {
k = j;
}
}
if (k != i) {
swap(array[i], array[k]);
}
}
}
#endif
#ifdef INSERTSORT
template<typename T>
void InsertSort(T array[], int len)
{
int i = 0;
int j = 0;
int k = -1;
int temp = -1;
for (i=1; i<len; i++) {
k = i;
temp = array[k];
for (j=i-1; (j>=0)&&(array[j]>temp); j--) {
array[j+1] = array[j];
k = j;
}
array[k] = temp;
}
}
#endif
#ifdef BUBBLESORT
template<typename T>
void BubbleSort(T array[], int len)
{
int i = 0;
int j = 0;
int exchange = 1;
for (i=0; i<len && exchange; i++) {
exchange = 0;
for (j=len-1; j>0; j--) {
if (array[j] < array[j-1]) {
Swap(array[j], array[j-1]);
exchange = 1;
}
}
}
}
#endif
#ifdef SHELLSORT
template<typename T>
void ShellSort(T array[], int len)
{
int i = 0;
int j = 0;
int k = 0;
int temp = 0;
int gap = len;
do {
gap = gap / 3 + 1;
for (i=gap; i<len; i+=gap) {
k = i;
temp = array[k];
for (j=i-gap; j>=0&&array[j]>temp; j-=gap) {
array[j+gap] = array[j];
k = j;
}
array[k] = temp;
}
} while (gap > 1);
}
#endif
#ifdef QUICKSORT
template<typename T>
int parition(T array[], int low, int high)
{
int pv = array[low];
while (low < high) {
while ((low<high) && (array[high] >= pv)) {
high--;
}
Swap(array[low], array[high]);
while ((low<high) && (array[low] <= pv)) {
low++;
}
Swap(array[low], array[high]);
}
return low;
}
template<typename T>
void QSort(T array[], int low, int high)
{
if (low < high) {
int part = parition(array, low, high);
QSort(array, low, part-1); //可以理解为左边数列
QSort(array, part+1, high); //可以理解为右边数列
}
}
template<typename T>
void QuickSort(T array[], int len)
{
QSort(array, 0, len-1);
}
#endif
#ifdef MERGESORT
template<typename T>
void Merge(T src[], T des[], int low, int mid, int high)
{
int i = low;
int j = mid+1;
int k = low;
while (i<=mid && j<=high) {
if (src[i] < src[j]) {
des[k++] = src[i++];
} else {
des[k++] = src[j++];
}
}
while (i<=mid) {
des[k++] = src[i++];
}
while (j<=high) {
des[k++] = src[j++];
}
}
template<typename T>
void MSort(T src[], T des[], int low, int high, int max)
{
if (low == high) {
des[low] = src[low];
} else {
int mid = (low + high) / 2;
T *space = (T *)malloc(sizeof(T)*max);
if (space != NULL) {
MSort(src, space, low, mid, max);
MSort(src, space, mid+1, high, max);
Merge(space, des, low, mid, high);
}
free(space);
space = NULL;
}
}
template<typename T>
void MergeSort(T array[], int len)
{
MSort(array, array, 0, len-1, len);
}
#endif
相关文章
- 作者:Sabine 【导读】本文介绍了C#的四种排序算法:冒泡排序、选择排序、插入排序和希尔排序 冒泡排序 using System; namespace BubbleSorter { public class Bubb...2020-06-25
图文详解Heap Sort堆排序算法及JavaScript的代码实现
这篇文章以图文详解Heap Sort堆排序算法及JavaScript的代码实现,堆排序算法基于类二叉树的堆数据结构,需要的朋友可以参考下...2016-05-05- 这篇文章主要为大家详细介绍了C/C++实现八大排序算法汇总,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2020-04-25
- 这篇文章主要介绍了C语言演示对归并排序算法的优化实现,归并排序的最差时间复杂度为(n\log n),最优时间复杂为(n),存在可以改进的空间,需要的朋友可以参考下...2020-04-25
- 冒泡排序和快速排序算法在开发应用中各有优点了,下面我们来看几个关于php排序的几个例子。 使用PHP描述冒泡排序和快速排序算法,对象可以是一个数组。 使用PHP描...2016-11-25
- 这篇文章主要为大家详细介绍了C++排序算法之插入排序,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2020-04-25
stl常用算法(Algorithms)介绍(stl排序算法、非变序型队列)
这篇文章主要介绍了stl常用算法(Algorithms)介绍(stl排序算法、非变序型队列),需要的朋友可以参考下...2020-04-25- 这篇文章主要介绍了堆排序算法(选择排序改进),有需要的朋友可以参考一下...2020-04-25
- function quickSort(&$data, $beg, $end) 02 { 03 if ($end > $beg) { 04 $piv = $data[$beg]; 05 $k = $beg + 1; 06 $r = $end; 07 while ($k < $r) { 08 if...2016-11-25
- 这篇文章主要介绍了一些常用排序算法整理,插入排序算法、直接插入排序、希尔排序、选择排序、冒泡排序等排序,需要的朋友可以参考下...2020-04-25
PHP常用排序算法实例小结【基本排序,冒泡排序,快速排序,插入排序】
小编推荐的这篇文章介绍了PHP常用排序算法实例小结,基本排序,冒泡排序,快速排序,插入排序,非常实用,有兴趣的同学快来看看吧。 代码如下复制代码classbevin{public$pub...2017-07-06- 这篇文章主要介绍了Java排序算法三之归并排序的递归与非递归的实现示例解析,文章通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-08-05
- 这篇文章主要介绍了php排序算法,结合实例形式分析了php数据查询、排序、数组去重、遍历与排序的相关操作技巧与注意事项,需要的朋友可以参考下...2016-10-20
- 这篇文章主要介绍了c语言实现奇偶排序算法,有需要的朋友可以参考一下...2020-04-25
- 这篇文章主要介绍了算法之排序算法的算法思想和使用场景总结,本文讲解了插入排序、交换排序、选择排序等几大类排序算法的特点、思想和使用场景,需要的朋友可以参考下...2020-04-25
- 一个快速排序算法代码一个快速排序算法代码,代码内有注释,大家参考使用吧...2020-04-25
- 这篇文章主要介绍了7种排序算法的实现示例,需要的朋友可以参考下...2020-04-25
- 本教程我们用PHP实例来讲解冒泡排序法,快速排序法,选择排序法,插入排序法等四大基础排序算法,我们的重点是给出算法思路,这种思路同样适用于其他编程语言。 四大基本排...2016-11-25
- php 常用的排序算法代码[冒泡,递归排序 冒泡排序算法 function bubblesort($arr) { $n=count($arr); for($i=0;$i<$n;$i++) { for($j=$i;$j<=$n-1;$j++) { if(...2016-11-25
- 这篇文章主要介绍了C语言基本排序算法之插入排序与直接选择排序实现方法,结合具体实例形式分析了插入排序与直接选择排序的定义、使用方法及相关注意事项,需要的朋友可以参考下...2020-04-25