首页 > 代码库 > 排序再学习 - 冒泡、快速、归并、堆排序

排序再学习 - 冒泡、快速、归并、堆排序

2024-07-28 07:05:14   224人阅读

1. 冒泡排序

每次比较数组中的两个数，如果和你期望的顺序不一致，就交换这两个数，一次循环下来能将一个数摆在正确的位置上。外层循环共需要N-1次，因为N-1个数都已经摆在正确的位置上，那第N个数也已经是正确的了。内层循环也可以是N-1次，也可以每次都比上一次少循环一次，第一种情况会比较已经排好序的部分，第二种情况已经排序过的部分不需要再比较了。还是两层循环都是N-1次比较好写。

void bubble_sort(int array[], int n){    int i, j, temp;    for ( i = 0; i < n - 1; i++ )    {        for ( j = 0; j < n - 1; j++ )        {            if ( array[j] > array[j+1] )            {                temp = array[j];                array[j] = array[j+1];                array[j+1] = temp;            }        }    }    return;}

 内层循环每次减少一次

 

void bubble_sort(int array[], int n){    int i, j, temp;    for ( i = 0; i < n - 1; i++ )    {        for ( j = 0; j < n - 1 - i; j++ )        {            if ( array[j] > array[j+1] )            {                temp = array[j];                array[j] = array[j+1];                array[j+1] = temp;            }        }    }    return;}

 2. 快速排序

在网上搜了几篇介绍快速排序的文章，个人感觉这篇《坐在马桶上看算法：快速排序》很不错，有图好理解。以下大部分内容均摘自此文章。

网址：http://developer.51cto.com/art/201403/430986.htm

快速排序的思想比较简单，整个排序过程分为三步：

  1. 在数组中选择一个元素作为基准值（pivot）
  2. 所有小于基准的元素，都移到基准的左边，大于基准的元素都移到基准的右边
  3. 对于基准的左边和右边的两个子集， 不断重复第一步和第二步，直到所有子集只剩下一个元素为止

待排序数组：6    1    2    7    9    3    4    5    10    8

　　1. 第一次选择最左边的6作为基准值

 

　　2. 从右边开始选择第一个小于6的数，下标递减，即j--

　　3. 从左边开始选择第一个大于6的数，下标递增，即i++

　　4. 交换这两个值，即交换7和5

     

     

　　5. 此时i != j,继续寻找

　　6. 第二次交换9和4

     

     

　　7. 再次寻找的话 i 就等于 j 了，这时交换基准值和array[i]

      

      

      

　　8. 这时6左边的数全部小于6,6右边的数全部大于6，接下来对这两个子序列进行同样的操作。

在写代码时要注意几个条件，开始扫描时，i必须总是小于j，i与j相等时则与基准值交换。另外，在递归调用时，判断low是否小于high，否则需要在quick_sort函数中对low和hign进行比较。

void quick_sort(int array[], int low, int high){    int base = array[low];    int i = low;    int j = high;    int temp;    while ( i != j )    {        /* 从右侧寻找第一个小于基准值的数 */        while ( array[j] >= base && i < j ) j--;        /* 从左侧寻找第一个大于基准值的数 */        while ( array[i] <= base && i < j ) i++;        if ( i != j )        {            temp = array[j];            array[j] = array[i];            array[i] = temp;        }    }    /* 此时i==j，和基准值交换 */    array[low] = array[i];    array[i] = base;    /* 继续对两个子序列进行同样的操作 */    if ( low < i - 1 )        quick_sort(array, low, i-1);    if ( i + 1 < high )        quick_sort(array, i+1, high);    return;}

 3. 归并排序

归并排序的核心思想是，将两个已经排序的子序列合并到一个序列中，时间复杂度为O(N)。如何得到有序的子序列呢？将整个序列进行二分，直到每个元素都是一个子序列。然后依次对每个子序列归并。分解过程采用递归的方式实现，时间复杂度为O(logN)，所以归并排序的时间复杂度为O(NlogN).

void merge_array(int array[], int low, int mid, int high){    int i = low, j = mid + 1;    int m = mid, n = high;    int k = 0;    int *temp = new int[high-low+1];        /* 将两个有序序列array[low...mid]和array[mid+1...high]合并*/    while ( i <= m && j <= n )    {        if ( array[i] <= array[j] )        {            temp[k++] = array[i++];        }        else        {            temp[k++] = array[j++];        }    }    /* 有一个序列会剩下，则将此序列的全部元素拷贝到临时数组中 */    while ( i <= m )     {        temp[k++] = array[i++];    }    while ( j <= n )    {        temp[k++] = array[j++];    }    /* 拷贝回原始数组中 */    for ( i = 0; i < k; i++ )    {        array[low+i] = temp[i];    }    delete [] temp;    return;}void merge_sort(int array[], int low, int high){    if ( low < high )    {        int mid = (low + high) / 2;        //printf("%d %d %d\r\n", low, mid, high);        merge_sort(array, low, mid);        merge_sort(array, mid+1,high);        merge_array(array, low, mid, high);    }    return;}

4. 堆排序

本节内容来自http://www.cnblogs.com/zabery/archive/2011/07/26/2117103.html

堆分为大根堆和小根堆，是完全二叉树，大根堆的要求是每个节点的值都不大于其父节点的值，在数组的非降序排序中，需要使用的就是大根堆，因为根据大根堆的要求可知，最大的值一定在堆顶。首先需要把数组转换成堆，并调整堆符合大根堆的要求。请看下图，数组为A = {1, 3, 4, 5, 7, 2, 6, 8, 0}

操作步骤

1. 数组A转换成堆为图1.1的形式,父节点的左叶子节点为 2*i+1, 右叶子节点是 2*i+2，i从0开始

2. 调堆的过程从最后一个非叶子节点开始，从图1.1可以看出，最后一个非叶子节点是A[3]=5

    如果数组有奇数个，则最后一个非叶子节点拥有两个孩子,即最后一个非叶子节点的右孩子为数组的最后一个值，则如下表达式成立 2*i+2 = n-1，得出i=(n-3)/2
    如果数组有偶数个，则最后一个非叶子节点拥有左孩子，这个左孩子为数组的最后一个值，2*i+1 = n-1，得出i=(n-2)/2
    由于除号只保留整数部分，所以这两个表达式计算得出的i是相等的，下面的代码中，我们把(n-2)/2作为最后一个非叶子节点

3. 图1.4与图1.3对比，3与8交换，此时3小于其左孩子5，所以3和5也要交换，得出图1.5. 图1.6到图1.7也有两次交换，所以调整堆时要注意大根堆的定义，即每个节点的值都不大于其父节点的值。要循环判断直到符合要求。

4. 每次调整堆结束后，堆的第一个元素都是当前堆的最大值，然后将此元素与堆的最后一个元素交换，堆元素的个数减一，继续调整堆，交换堆首元素与堆的最后一个元素，如此反复，直到堆的元素个数还剩1，排序完成

/*     n:元素个数    i:需要比较的子树的根节点*/void adjust_heap(int array[], int n, int i){    int    left  = 2 * i + 1;    int right = 2 * i + 2;    int largest = i;    int temp;    while ( left < n || right < n )    {        /* 找到根节点和两个叶子节点中最大的值 */        if ( left < n && array[largest] < array[left] )        {            largest = left;        }        if ( right < n && array[largest] < array[right] )        {            largest = right;        }        /* 如果根节点不是最大值，则与最大值交换 */        if ( largest != i )        {            temp = array[largest];            array[largest] = array[i];            array[i] = temp;            /* 操作步骤3的实现，循环比较整个子树是否符合要求 */            i = largest;            left  = 2 * i + 1;            right = 2 * i + 2;        }        else        {            break;        }    }    return;}void build_heap(int array[], int n){    int i;    /* 操作步骤2的实现，从最后一个非叶子节点开始调整堆，直到根节点 */    for ( i = (n - 2)/2; i >= 0; i-- )    {        adjust_heap(array, n, i);    }    return;}void heap_sort(int array[], int n){    int i, temp;        build_heap(array, n);    /* 步骤4的实现，每次循环交换堆的第一个元素与最后一个元素，堆大小每次减1，       由于每次调整堆，堆的第一个元素都是当前堆的最大值，交换后就得到一个排       好序的数组 */    for ( i = n - 1; i > 0; i-- )    {        temp = array[0];        array[0] = array[i];        array[i] = temp;        adjust_heap(array, i, 0);    }    return;}

 

排序再学习 - 冒泡、快速、归并、堆排序


联系
我们