十种排序算法总结(冒泡、插入、选择、希尔、归并、堆、快速,计数,桶,基数)

#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;
}

(0)

相关推荐