排序算法模板实现示例分享

代码如下:

#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

赞 (0)

相关推荐

  • c# 快速排序算法

    c# 快速排序算法

    快速排序使用分治法(Divide and conquer)策略来把一个串行(list)分为两个子串行(sub-lists). 步骤为: 1.从数列中挑出一个元素,称为 "基准"(pivot), 2.重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边).在这个分区退出之后,该基准就处于数列的中间位置.这个称为分区(partition)操作. 3.递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序. 递归

  • c语言快速排序算法示例代码分享

    步骤为:1.从数列中挑出一个元素,称为 "基准"(pivot);2.重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边).在这个分区退出之后,该基准就处于数列的中间位置.这个称为分区(partition)操作.3.递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序.递归的最底部情形,是数列的大小是零或一,也就是永远都已经被排序好了.虽然一直递归下去,但是这个算法总会退出,因为在每次的迭代(iterat

  • python实现排序算法

    复制代码 代码如下: def insertion_sort(n):    if len(n) == 1:        return n    b = insertion_sort(n[1:])    m = len(b)    for i in range(m):        if n[0] <= b[i]:            return b[:i]+[n[0]]+b[i:]    return b + [n[0]]l = [1,3,4,2,6,7,9,7,12,11,789,345,

  • python算法学习之桶排序算法实例(分块排序)

    复制代码 代码如下: # -*- coding: utf-8 -*- def insertion_sort(A):    """插入排序,作为桶排序的子排序"""    n = len(A)    if n <= 1:        return A    B = [] # 结果列表    for a in A:        i = len(B)        while i > 0 and B[i-1] > a:      

  • c语言实现奇偶排序算法

    =====第2题:奇偶排序(一)===== 总时间限制:1000ms内存限制:65536kB描述输入十个整数,将十个整数按升序排列输出,并且奇数在前,偶数在后.输入输入十个整数输出按照奇偶排序好的十个整数 复制代码 代码如下: #include<stdio.h> #define  COUNT 10#define bool int#define true 1#define false 0 /*****负责冒泡排序***/int* sortFunction(int data[]){ int i,j

  • 常用排序算法整理分享(快速排序算法、希尔排序)

    整理了几个排序算法,通过测试来看,最快的还是快速排序算法,简直不是一个数量级的速度. 复制代码 代码如下: #include <stdio.h>#include <stdlib.h>#include <stdint.h>#include <stdbool.h>#include <time.h>#include <unistd.h> //一些排序算法整理//插入排序算法//直接插入排序voiddirect_insert_sort(int

  • 一个快速排序算法代码分享

    复制代码 代码如下: /* * quickSort.c * *  Created on: 2012-4-9 *      Author: LW */#include <stdio.h>#include <string.h> typedef struct _student{ int id; char name[30];}student,*pStudent; student students[20] ={ {13,"狐狸金"},{15,"杜十娘"

  • C++中的几种排序算法

    SortAlgorithm.h 复制代码 代码如下: #include <vector>using namespace std; class SortAlgorithm{public:    SortAlgorithm(int = 10);    void displayVector();    void swap(int &, int &); void insertSort();                     //O(n^2)    void selectSort(

  • 排序算法模板实现示例分享

    复制代码 代码如下: #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

  • Java实现世界上最快的排序算法Timsort的示例代码

    Java实现世界上最快的排序算法Timsort的示例代码

    目录 背景 前置知识 指数搜索 二分插入排序 归并排序 Timsort 执行过程 升序运行 几个关键阀值 运行合并 合并条件 合并内存开销 合并优化 背景 Timsort 是一个混合.稳定的排序算法,简单来说就是归并排序和二分插入排序算法的混合体,号称世界上最好的排序算法.Timsort一直是 Python 的标准排序算法.Java SE 7 后添加了Timsort API ,我们从Arrays.sort可以看出它已经是非原始类型数组的默认排序算法了.所以不管是进阶编程学习还是面试,理解 Tim

  • TypeScript实现十大排序算法之冒泡排序示例详解

    目录 一. 冒泡排序的定义 二. 冒泡排序的流程 三. 冒泡排序的图解 四. 冒泡排序的代码 五. 冒泡排序的时间复杂度 六. 冒泡排序的总结 一. 冒泡排序的定义 冒泡排序是一种简单的排序方法. 基本思路是通过两两比较相邻的元素并交换它们的位置,从而使整个序列按照顺序排列. 该算法一趟排序后,最大值总是会移到数组最后面,那么接下来就不用再考虑这个最大值. 一直重复这样的操作,最终就可以得到排序完成的数组. 这种算法是稳定的,即相等元素的相对位置不会发生变化. 而且在最坏情况下,时间复杂度为O(

  • Python实现各种排序算法的代码示例总结

    Python实现各种排序算法的代码示例总结

    在Python实践中,我们往往遇到排序问题,比如在对搜索结果打分的排序(没有排序就没有Google等搜索引擎的存在),当然,这样的例子数不胜数.<数据结构>也会花大量篇幅讲解排序.之前一段时间,由于需要,我复习了一下排序算法,并用Python实现了各种排序算法,放在这里作为参考. 最简单的排序有三种:插入排序,选择排序和冒泡排序.这三种排序比较简单,它们的平均时间复杂度均为O(n^2),在这里对原理就不加赘述了.贴出来源代码. 插入排序: def insertion_sort(sort_lis

  • 使用Java实现希尔排序算法的简单示例

    简介 希尔排序(缩小增量法) 属于插入类排序,由Shell提出,希尔排序对直接插入排序进行了简单的改进:它通过加大插入排序中元素之间的间隔,并在这些有间隔的元素中进行插入排序,从而使数据项大跨度地移动,当这些数据项排过一趟序之后,希尔排序算法减小数据项的间隔再进行排序,依次进行下去,进行这些排序时的数据项之间的间隔被称为增量,习惯上用字母h来表示这个增量. 常用的h序列由Knuth提出,该序列从1开始,通过如下公式产生: h = 3 * h +1 反过来程序需要反向计算h序列,应该使用 h=(h

  • JAVA版排序算法之快速排序示例

    本文实例讲述了JAVA快速排序实现方法.分享给大家供大家参考,具体如下: package com.ethan.sort.java; import java.util.Arrays; import java.util.Iterator; import java.util.LinkedList; import java.util.List; public class QuickSort { public static <E extends Comparable<? super E>>

  • Python八大常见排序算法定义、实现及时间消耗效率分析

    本文实例讲述了Python八大常见排序算法定义.实现及时间消耗效率分析.分享给大家供大家参考,具体如下: 昨晚上开始总结了一下常见的几种排序算法,由于之前我已经写了好几篇排序的算法的相关博文了现在总结一下的话可以说是很方便的,这里的目的是为了更加完整详尽的总结一下这些排序算法,为了复习基础的东西,从冒泡排序.直接插入排序.选择排序.归并排序.希尔排序.桶排序.堆排序.快速排序入手来分析和实现,在最后也给出来了简单的时间统计,重在原理.算法基础,其他的次之,这些东西的熟练掌握不算是对之后的工作或者

  • python实现的希尔排序算法实例

    本文实例讲述了python实现希尔排序算法的方法.分享给大家供大家参考.具体如下: def shellSort(items): inc = len(items) / 2 while inc: for i in xrange(len(items)): j = i temp = items[i] while j >= inc and items[j-inc] > temp: items[j] = items[j - inc] j -= inc items[j] = temp inc = inc/2

  • java数据结构排序算法之归并排序详解

    本文实例讲述了java数据结构排序算法之归并排序.分享给大家供大家参考,具体如下: 在前面说的那几种排序都是将一组记录按关键字大小排成一个有序的序列,而归并排序的思想是:基于合并,将两个或两个以上有序表合并成一个新的有序表 归并排序算法:假设初始序列含有n个记录,首先将这n个记录看成n个有序的子序列,每个子序列长度为1,然后两两归并,得到n/2个长度为2(n为奇数的时候,最后一个序列的长度为1)的有序子序列.在此基础上,再对长度为2的有序子序列进行亮亮归并,得到若干个长度为4的有序子序列.如此重

  • php实现希尔排序算法的方法分析

    本文实例讲述了php实现希尔排序算法的方法.分享给大家供大家参考,具体如下: 虽然现在各种程序语言都有其各自强大的排序库函数,但是这些底层实现也都是利用这些基础或高级的排序算法. 理解这些复杂的排序算法还是很有意思的,体会这些排序算法的精妙~ 希尔排序(shell sort):希尔排序是基于插入排序的,区别在于插入排序是相邻的一个个比较(类似于希尔中h=1的情形),而希尔排序是距离h的比较和替换. 希尔排序中一个常数因子n,原数组被分成各个小组,每个小组由h个元素组成,很可能会有多余的元素.当然

随机推荐