`
隐形的翅膀
  • 浏览: 497351 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

十种排序算法总结

 
阅读更多
http://blog.csdn.net/jnu_simba/article/details/9705111

#include<iostream>
using namespace std;

void swap1(int *left, int *right)
{
    int temp = *left;
    *left = *right;
    *right = temp;
}

void swap2(int &left, int &right)
{
    int temp = left;
    left = right;
    right = left;
}

void swap3(int &left, int &right)
{
    if (&left != &right) 
    {
        left ^= right;
        right ^= left;
        left ^= right;
    }
}

/*****************************************************************/
/* 冒泡排序时间复杂度最好的情况为O(n),最坏的情况是O(n^2)
* 基本思想是:两两比较相邻记录的关键字,如果反序则交换 */

void BubbleSort1(int arr[], int num)
{
    int i, j;
    for (i = 0; i < num; i++)
    {
        for (j = 1; j < num - i; j++)
        {
            if (arr[j - 1] > arr[j])
                swap1(&arr[j - 1], &arr[j]);
        }
    }
}

// 改进思路:设置标志位,明显如果有一趟没有发生交换(flag = flase),说明排序已经完成.
void BubbleSort2(int arr[], int num)
{
    int k = num;
    int j;
    bool flag = true;
    while (flag)
    {
        flag = false;
        for (j = 1; j < k; j++)
        {
            if (arr[j - 1] > arr[j])
            {
                swap1(&arr[j - 1], &arr[j]);
                flag = true;
            }
        }
        k--;
    }
}
//改进思路:记录一轮下来标记的最后位置,下次从头部遍历到这个位置就Ok
void BubbleSort3(int arr[], int num)
{
    int k, j;
    int flag = num;
    while (flag > 0)
    {
        k = flag;
        flag = 0;
        for (j = 1; j < k; j++)
        {
            if (arr[j - 1] > arr[j])
            {
                swap1(&arr[j - 1], &arr[j]);
                flag = j;
            }
        }
    }
}
/*************************************************************************/

/**************************************************************************/
/*插入排序: 将一个记录插入到已经排好序的有序表中, 从而得到一个新的,记录数增1的有序表
* 时间复杂度也为O(n^2), 比冒泡法和选择排序的性能要更好一些 */

void InsertionSort(int arr[], int num)
{
    int temp;
    int i, j;
    for (i = 1; i < num; i++)
    {
        temp = arr[i];
        for (j = i; j > 0 && arr[j - 1] > temp; j--)
            arr[j] = arr[j - 1];
        arr[j] = temp;
    }
}

/****************************************************************************/

/*希尔排序:先将整个待排元素序列分割成若干子序列(由相隔某个“增量”的元素组成的)分别进行
直接插入排序,然后依次缩减增量再进行排序,待整个序列中的元素基本有序(增量足够小)时,
再对全体元素进行一次直接插入排序(增量为1)。其时间复杂度为O(n^3/2),要好于直接插入排序的O(n^2) */
void ShellSort(int *arr, int N)
{
    int i, j, increment;
    int tmp;
    for (increment = N / 2; increment > 0; increment /= 2)
    {
        for (i = increment; i < N; i++)
        {
            tmp = arr[i];
            for (j = i; j >= increment; j -= increment)
            {
                if (arr[j - increment] > tmp)
                    arr[j] = arr[j - increment];
                else
                    break;
            }
            arr[j] = tmp;
        }

    }
}

/**************************************************************************/

/* 简单选择排序(simple selection sort) 就是通过n-i次关键字之间的比较,从n-i+1
* 个记录中选择关键字最小的记录,并和第i(1<=i<=n)个记录交换之
* 尽管与冒泡排序同为O(n^2),但简单选择排序的性能要略优于冒泡排序 */

void SelectSort(int arr[], int num)
{
    int i, j, Mindex;
    for (i = 0; i < num; i++)
    {
        Mindex = i;
        for (j = i + 1; j < num; j++)
        {
            if (arr[j] < arr[Mindex])
                Mindex = j;
        }

        swap1(&arr[i], &arr[Mindex]);
    }
}

/********************************************************************************/
/*假设初始序列含有n个记录,则可以看成n个有序的子序列,每个子序列的长度为1,然后
* 两两归并,得到(不小于n/2的最小整数)个长度为2或1的有序子序列,再两两归并,...
* 如此重复,直至得到一个长度为n的有序序列为止,这种排序方法称为2路归并排序
* 时间复杂度为O(nlogn),空间复杂度为O(n+logn),如果非递归实现归并,则避免了递归时深度为logn的栈空间
* 空间复杂度为O(n) */


/*lpos is the start of left half, rpos is the start of right half*/
void merge(int a[], int tmp_array[], int lpos, int rpos, int rightn)
{
    int i, leftn, num_elements, tmpos;

    leftn = rpos - 1;
    tmpos = lpos;
    num_elements = rightn - lpos + 1;

    /*main loop*/
    while (lpos <= leftn && rpos <= rightn)
        if (a[lpos] <= a[rpos])
            tmp_array[tmpos++] = a[lpos++];
        else
            tmp_array[tmpos++] = a[rpos++];

    while (lpos <= leftn) /*copy rest of the first part*/
        tmp_array[tmpos++] = a[lpos++];
    while (rpos <= rightn) /*copy rest of the second part*/
        tmp_array[tmpos++] = a[rpos++];

    /*copy array back*/
    for (i = 0; i < num_elements; i++, rightn--)
        a[rightn] = tmp_array[rightn];
}


void msort(int a[], int tmp_array[], int left, int right)
{
    int center;

    if (left < right)
    {
        center = (right + left) / 2;
        msort(a, tmp_array, left, center);
        msort(a, tmp_array, center + 1, right);
        merge(a, tmp_array, left, center + 1, right);
    }
}



void merge_sort(int a[], int n)
{
    int *tmp_array;
    tmp_array = (int *)malloc(n * sizeof(int));

    if (tmp_array != NULL)
    {
        msort(a, tmp_array, 0, n - 1);
        free(tmp_array);
    }

    else
        printf("No space for tmp array!\n");
}

/************************************************************************************/
/* 堆是具有下列性质的完全二叉树:每个节点的值都大于或等于其左右孩子节点的值,称为大顶堆;
* 或者每个节点的值都小于或等于其左右孩子节点的值,称为小顶堆*/

/*堆排序就是利用堆进行排序的方法.基本思想是:将待排序的序列构造成一个大顶堆.此时,整个序列的最大值就是堆顶
* 的根结点.将它移走(其实就是将其与堆数组的末尾元素交换, 此时末尾元素就是最大值),然后将剩余的n-1个序列重新
* 构造成一个堆,这样就会得到n个元素的次大值.如此反复执行,便能得到一个有序序列了
*/
/* 时间复杂度为 O(nlogn),好于冒泡,简单选择,直接插入的O(n^2) */

// 构造大顶堆
#define leftChild(i) (2*(i) + 1)

void percDown(int *arr, int i, int N)
{
    int tmp, child;
    for (tmp = arr[i]; leftChild(i) < N; i = child)
    {
        child = leftChild(i);
        if (child != N - 1 && arr[child + 1] > arr[child])
            child++;
        if (arr[child] > tmp)
            arr[i] = arr[child];
        else
            break;
    }
    arr[i] = tmp;
}

void HeapSort(int *arr, int N)
{
    int i;
    for (i = N / 2; i >= 0; i--)
        percDown(arr, i, N);
    for (i = N - 1; i > 0; i--)
    {
        swap1(&arr[0], &arr[i]);
        percDown(arr, 0, i);
    }
}


int main(void)
{
    int arr[] = { 9, 2, 5, 8, 3, 4, 7, 1, 6, 10};
    HeapSort(arr, 10);
    for (int i = 0; i < 10; i++)
        cout << arr[i] << ' ';
    cout << endl;

    return 0;
}
分享到:
评论

相关推荐

    常用排序算法总结 常用排序算法总结 常用排序算法总结

    常用排序算法总结常用排序算法总结常用排序算法总结常用排序算法总结常用排序算法总结常用排序算法总结常用排序算法总结常用排序算法总结常用排序算法总结常用排序算法总结

    十种排序算法介绍十种排序算法介绍

    ### 十种排序算法介绍 #### 一、概述 本文旨在详细介绍十种常见的排序算法,这些算法不仅是计算机科学的基础组成部分,也是数据结构课程中的重要内容。排序算法被广泛应用于各种场景,如数据库管理、搜索引擎结果...

    几种排序算法总结及比较

    这里我们将深入探讨几种常见的排序算法,并在VS2013环境下进行实现和比较。 1. 冒泡排序(Bubble Sort) 冒泡排序是一种简单的交换排序,它通过重复遍历待排序的数列,依次比较相邻元素并根据需要交换位置,直到...

    十大经典排序算法总结.docx

    《十大经典排序算法总结》 排序算法是计算机科学的基础,其设计思想和效率对软件的性能有着直接影响。本文主要探讨了十种经典的排序算法,包括它们的设计思路、优缺点以及适用场景,帮助我们理解排序算法的核心。 ...

    C#排序算法总结

    C#排序算法总结涵盖了交换排序和插入排序两大类排序算法,其中交换排序包括了冒泡排序、选择排序和快速排序,而插入排序则涉及直接插入排序和折半插入排序。下面将详细介绍每种排序算法的实现原理、特点以及在C#中的...

    八大排序算法总结

    【排序算法总结】 排序是计算机科学中的一项基本操作,它涉及到如何有效地重新排列一组数据,使其按照特定的顺序排列。本文将重点介绍八大排序算法,包括插入排序、希尔排序、交换排序、快速排序、选择排序、堆排序...

    排序算法总结.doc

    以下是对几种常见排序算法的详细说明: 1. 插入排序: 插入排序是一种简单的排序算法,其时间复杂度为O(n^2)。它通过将每个元素插入到已排序的部分中找到正确位置来工作,保持已排序部分的稳定性。当数组近乎有序...

    常用的排序算法总结(各种内部排序算法和外部排序算法)

    本文将对几种常见的内部排序算法和外部排序算法进行详细总结。 首先,排序的基本定义是:给定一个包含n个记录的序列,其关键字序列分别为K1, K2, ..., Kn,如果存在一个排列p1, p2, p3, ..., pn,使得关键字满足非...

    各种排序算法总结(ppt)

    在这个名为“各种排序算法总结(ppt)”的资料中,我们将会深入探讨多种常见的排序算法,包括它们的基本原理、优缺点以及实际应用。** 首先,我们要了解排序的目的是为了使数据有序,这在数据处理和分析中具有广泛...

    八大经典排序算法总结和源代码

    八大经典排序算法总结和源代码 在计算机科学中,排序算法是最基本也是最重要的算法之一。排序算法的性能直接影响到整个系统的性能。今天,我们将总结八大经典排序算法,并提供C++实现的源代码。 一、稳定排序和...

    八种常见排序算法总结(转)

    "八种常见排序算法总结" 直接插入排序是一种简单的排序算法,它的思想是每次选择一个元素 K 插入到之前已排好序的部分 A[1…i]中,插入过程中 K 依次由后向前与 A[1…i]中的元素进行比较。若发现 A[x]&gt;=K,则将 K ...

    几种内部排序算法总结

    ### 几种内部排序算法总结 #### 冒泡排序(Bubble Sort) 冒泡排序是一种简单的排序算法,它重复地遍历待排序的数列,依次比较相邻的两个元素,如果它们的顺序错误就把它们交换过来。遍历数列的工作是重复进行的,...

    10种排序算法总结

    本文将对10种常见的排序算法进行总结,帮助你理解它们的工作原理、效率以及适用场景。 首先,冒泡排序是一种简单的排序算法,其核心思想是通过不断交换相邻的错误顺序元素来逐步排序。它的时间复杂度为O(n²),适合...

    排序算法总结和比较

    本文主要总结和比较了九种常见的排序算法:快速排序、归并排序、堆排序、Shell排序、插入排序、冒泡排序、交换排序、选择排序以及基数排序。 1. **快速排序**:快速排序是一种基于分治思想的高效排序算法,由C.A.R....

    常用排序算法总结

    ### 常用排序算法总结 #### 一、冒泡排序 冒泡排序是一种简单的排序算法,它重复地遍历待排序的数列,依次比较相邻的两个元素,如果他们的顺序错误就把他们交换过来。遍历数列的工作是重复进行的,直到没有再需要...

    数据结构中几种常用的排序算法总结

    ### 数据结构中几种常用的排序算法总结 #### 一、引言 在计算机科学与数学领域,排序算法是一种能够按照特定顺序(如数值顺序或字典顺序)排列一系列数据的算法。排序算法对于许多其他算法(如搜索算法和合并算法)...

    经典排序算法总结

    以下是对几种经典排序算法的详细解释和C++实现: 1. **冒泡排序**: 冒泡排序是最基础的排序算法之一,通过不断交换相邻的逆序元素来逐步将大的元素“冒”到序列末尾。时间复杂度为O(n^2)。 ```cpp template void...

    常见排序算法总结.pdf

    【排序算法总结】 排序算法是计算机科学中处理数据排列的重要工具,主要分为稳定排序和非稳定排序、内排序和外排序两大类。稳定排序保证了相同元素在排序后的相对位置不变,而非稳定排序则不作此保证。内排序是指...

Global site tag (gtag.js) - Google Analytics