几种常见排序算法的比较与实现

几种常见排序算法的比较与实现
1冒泡排序（Bubble Sort）
冒泡排序方法是最简单的排序方法。这种方法的基本思想是，将待排序的元素看作是竖着排列的“气泡”，较小的元素比较轻，从而要往上浮。在冒泡排序算法中我们要对这个“气泡”序列处理若干遍。所谓一遍处理，就是自底向上检查一遍这个序列，并时刻注意两个相邻的元素的顺序是否正确。如果发现两个相邻元素的顺序不对，即“轻”的元素在下面，就交换它们的位置。显然，处理一遍之后，“最轻”的元素就浮到了最高位置；处理二遍之后，“次轻”的元素就浮到了次高位置。在作第二遍处理时，由于最高位置上的元素已是“最轻”元素，所以不必检查。一般地，第i遍处理时，不必检查第i高位置以上的元素，因为经过前面i-1遍的处理，它们已正确地排好序。
冒泡排序是稳定的。算法时间复杂度是O(n^2)。
2选择排序（Selection Sort）
选择排序的基本思想是对待排序的记录序列进行n-1遍的处理，第i遍处理是将L[i..n]中最小者与L[i]交换位置。这样，经过i遍处理之后，前i个记录的位置已经是正确的了。
选择排序是不稳定的。算法复杂度是O(n^2 )。
3插入排序（Insertion Sort）
插入排序的基本思想是，经过i-1遍处理后,L[1..i-1]己排好序。第i遍处理仅将L[i]插入L[1..i-1]的适当位置，使得L[1..i]又是排好序的序列。要达到这个目的，我们可以用顺序比较的方法。首先比较L[i]和L[i-1]，如果L[i-1]≤ L[i]，则L[1..i]已排好序，第i遍处理就结束了；否则交换L[i]与L[i-1]的位置，继续比较L[i-1]和L[i-2]，直到找到某一个位置j(1≤j≤i-1)，使得L[j] ≤L[j+1]时为止。图1演示了对4个元素进行插入排序的过程，共需要(a),(b),(c)三次插入。
直接插入排序是稳定的。算法时间复杂度是O(n^2)
4堆排序
堆排序是一种树形选择排序，在排序过程中，将A[n]看成是完全二叉树的顺序存储结构，利用完全二叉树中双亲结点和孩子结点之间的内在关系来选择最小的元素。
堆排序是不稳定的。算法时间复杂度O(nlog n)。
5归并排序
设有两个有序（升序）序列存储在同一数组中相邻的位置上，不妨设为A[l..m]，A[m+1..h]，将它们归并为一个有序数列，并存储在A[l..h]。
其时间复杂度无论是在最好情况下还是在最坏情况下均是O(nlog2n)。
6快速排序
快速排序是对冒泡排序的一种本质改进。它的基本思想是通过一趟扫描后，使得排序序列的长度能大幅度地减少。在冒泡排序中，一次扫描只能确保最大数值的数移到正确位置，而待排序序列的长度可能只减少1。快速排序通过一趟扫描，就能确保某个数（以它为基准点吧）的左边各数都比它小，右边各数都比它大。然后又用同样的方法处理它左右两边的数，直到基准点的左右只有一个元素为止。
快速排序是不稳定的。最理想情况算法时间复杂度O(nlog2n)，最坏O(n ^2)。
7希尔排序
在直接插入排序算法中，每次插入一个数，使有序序列只增加1个节点，并且对插入下一个数没有提供任何帮助。如果比较相隔较远距离（称为增量）的数，使得数移动时能跨过多个元素，则进行一次比较就可能消除多个元素交换。D.L.shell于1959年在以他名字命名的排序算法中实现了这一思想。算法先将要排序的一组数按某个增量d分成若干组，每组中记录的下标相差d.对每组中全部元素进行排序，然后再用一个较小的增量对它进行，在每组中再进行排序。当增量减到1时，整个要排序的数被分成一组，排序完成。
希尔排序是不稳定的。算法时间复杂度是O(n^2)。
例如：假设待排序文件有10个记录，其关键字分别是：
        49，38，65，97，76，13，27，49，55，04。
    　增量序列的取值依次为：
        5，3，1
按增量5分两组。第一次排序后结果为：
13，27，49，55，04， 49，38，65，97，76，
按增量3分组，第二次排序后结果为：
13，04，49，38，27，49，55，65，97，76
按增量1分组，第三次排序后结果为：
04,13,27,38,49,49,55,65,76,97
3.常见算法复杂度比较

  序号
排序类别
时间复杂度
空间复杂度
稳定

1
插入排序
O(n2)
1
√

2
希尔排序
O(n2)
1
×

3
冒泡排序
O(n2)
1
√

4
选择排序
O(n2)
1
×

5
快速排序
O(Nlogn)
O(logn)
×

6
堆排序
O(Nlogn)
1
×

7
归并排序
O(Nlogn)
O(n)
√

#include <iostream> #include <ctime>
const int SIZE = 100;
const int MAX = 1000;
using namespace std;

//交换数据
void Swap(int &a, int &b)
{
    int temp = a;
    a = b;
    b = temp;
}

//冒泡排序
void BubbleSort(int *arr, int size) { int i, j;
    for(i=0;i<size-1;i++)
        for(j=size-1;j>i;j--)//最先从arr[0]开始排序
           // for(j=0;j<size-i-1;j++)  //最先从arr[size-1]开始排序
     if(arr[j] < arr[j-1])
                Swap(arr[j], arr[j-1]);
}


//选择排序
void SelectionSort(int *arr, int size)
{
    int i, j, min;
    //找出从a[i]到a[size-1]的最小元素的位置
    for(i=0;i<size-1;i++)
    {
        min = i;
        for(j=i+1;j<size;j++)
            if(arr[min] > arr[j])
                min = j;
        //将a[i]与a[min]的数据交换
        Swap(arr[i], arr[min]);
    }
}
:方法2：
void choiseSort(int *a,int n)
{
    int i,j,k,temp;
    for(i=0;i<n-1;i++)
    {
       k=i; /*给记号赋值*/
       for(j=i+1;j<n;j++)
          if(a[k]>a[j]) k=j; /*是k总是指向最小元素*/
          if(i!=k) //当k!=i时才交换，否则a即为最小
{
                temp=a;
                a=a[k];
                a[k]=temp;
            }
    }
}


//插入排序

void InsertSort(int *arr, int size)
{
    int fOut, loc, temp;
    for(fOut = 1; fOut < size; fOut++)
        if(arr[fOut]<arr[fOut-1])
        {
            temp = arr[fOut];
            loc = fOut;
            do
            {
                arr[loc] = arr[loc-1];
                loc--;
            }while(loc>0 && arr[loc-1]>temp);
            arr[loc] = temp;
        }
}

//快速排序
快速法定义了三个参数，（数组首地址*a,要排序数组起始元素下标i,要排序数组结束元素下标j). 它首先选一个数组元素（一般为a[(i+j)/2],即中间元素）作为参照，把比它小的元素放到它的左边，比它大的放在右边。然后运用递归，在将它左，右两个子数组排序，最后完成整个数组的排序。
int Partition(int *arr, int first, int last)
{
    int i, small, x;
    //为了减少最差情况的出现频率而作的一种优化
    swap(arr[first], arr[ (first+last)/2 ]);
    x = arr[first];
    small = first;
    for(i=first+1;i<=last;i++)
        if(arr[i] < x)
        {
            small++;
            swap(arr[small], arr[i]);
        }
        swap(arr[first], arr[small]);
        return small;
}

void RecQuick(int *arr, int first, int last)
{
      int pivotPos;

   if(first<last)
   {
       pivotPos=Partition(arr,first,last);
       RecQuick(arr,first,pivotPos-1);
       RecQuick(arr,pivotPos+1,last);
   }
}

void QuickSort(int *arr, int size)
{
    RecQuick(arr, 0, size-1);
}


//计数排序
void CountSort(int *arr, int size)
{
    int temp[MAX] = {0};
    int i, j;
    for(i=0;i<size;i++)
        temp[arr[i]]++;
    j = 0;
    for(i=0;i<MAX;i++)
    {
        while(0 != temp[i])
        {
            arr[j] = i;
            temp[i]--;
            j++;
        }
    }
}

//归并排序
void Merge(int *arr, int start, int mid, int end)
{
    int temp1[SIZE], temp2[SIZE];
    int n1, n2;
    int i, j, k;
    n1 = mid - start + 1;
    n2 = end - mid;
    //拷贝前半部分数组
    for(i=0;i<n1;i++)
        temp1[i] = arr[start + i];
    //拷贝后半部分数组
    for(i=0;i<n2;i++)
        temp2[i] = arr[mid + i + 1];
    //把后面的元素设置的很大
    temp1[n1] = temp2[n2] = INT_MAX;
    i = j = 0;
    // 逐个扫描两部分数组然后放到相应的位置去
    for(k=start;k<=end;k++)
    {
        if(temp1[i] <= temp2[j])
        {
            arr[k] = temp1[i];
            i++;
        }
        else
        {
            arr[k] = temp2[j];
            j++;
        }
    }
}
//堆排序
void Heapify(int *arr, int low, int high)
{
    int large;
    int temp = arr[low];
    large = 2 * low + 1;
    while(large <= high)
    {
        if(large<high && arr[large]<arr[large+1])
            large = large + 1;
        if(temp > arr[large])
            break;
        else
        {
            arr[low] = arr[large];
            low = large;
            large = 2 * low + 1;
        }
    }
    arr[low] = temp;
}

void BuildHeap(int *arr, int size)
{
    int i;
    for(i=size/2-1;i>=0;i--)
        Heapify(arr, i, size-1);
}

void HeapSort(int *arr, int size)
{
    int i;        //lastOfOrder
    BuildHeap(arr, size);
    for(i=size-1;i>=0;i--)
    {
        swap(arr[0], arr[i]); Heapify(arr, 0, i-1);
    }
}

//希尔排序
void ShellSort(int *arr, int size)
{
    int i, j, k, temp;
    //i为增量
    for(i=size/2;i>0;i/=2)
    {
        for(j=i;j<size;j+=i)
        {
            temp = arr[j];
            k = j;
            while(k-i>=0 && temp<arr[k-i])
            {
                arr[k] = arr[k-i];
                k -= i;
            }
            arr[k] = temp;
        }
    }
}