常见排序及实现

常见排序及实现

1.常见排序算法

1）插入排序：直接插入排序，希尔排序

2）选择排序：选择排序，堆排序

3）交换排序：冒泡排序，快速排序

4）归并排序：归并排序

排序接口的实现

void InsertSort ( int* a , int n ); // 插入排序 void ShellSort ( int* a , int n ); // 希尔排序 void SelectSort ( int* a , int n ); // 选择排序 void AdjustDwon ( int* a , int n , int root ); void HeapSort ( int* a , int n ); // 堆排序 void BubbleSort ( int* a , int n )； // 冒泡排序 // 快速排序递归实现 // 快速排序 hoare 版本 int PartSort1 ( int* a , int left , int right ); // 快速排序挖坑法 int PartSort2 ( int* a , int left , int right ); // 快速排序前后指针法 int PartSort3 ( int* a , int left , int right ); void QuickSort ( int* a , int left , int right ); // 快速排序 非递归实现 void QuickSortNonR ( int* a , int left , int right); // 归并排序递归实现 void MergeSort ( int* a , int n ); // 计数排序 void CountSort ( int* a , int n)

2.直接插入排序

 void InsertSort(int* a, int n)
{
    for (int i = 0; i < n - 1; ++i)
    {
        //[0,end]有序，把end+1位置的值插入，保持有序
        int end = i;
        int tmp = a[end + 1];
        while (end >= 0)
        {
            if (tmp < a[end])
            {
                a[end + 1] = a[end];
                --end;
            }
            else
            {
                break;
            }
        }
        a[end + 1] = tmp;
    }
}

直接插入排序的特性总结： 

1. 元素集合越接近有序，直接插入排序算法的时间效率越高 2. 时间复杂度： O(N^2) 3. 空间复杂度： O(1) ，它是一种稳定的排序算法 4. 稳定性：稳定

3.希尔排序（缩小增量排序）

void ShellSort(int* a, int n)
{
    //gap > 1时是预排序
    //gap 最后一次等于1，是直接插入排序
    int gap = n;
    while (gap > 1)
    {
        gap = gap / 3 + 1;
        for (int i = 0; i < n - gap; ++i)
        {
            int end = i;
            int tmp = a[end + gap];
            while (end >= 0)
            {
                if (tmp < a[end])
                {
                    a[end + gap] = a[end];
                    end -= gap;
                }
                else
                {
                    break;
                }
            }
            a[end + gap] = tmp;
        }
    }
}

4.选择排序

 void SelectSort(int* a, int n)
{
    assert(a);
    int begin = 0, end = n - 1;
    while(begin<end)
    {
        int mini = begin, maxi = begin;
        for (int i = begin + 1; i <= end; ++i)
        {
            if (a[i] < a[mini])
                mini = i;
            if (a[i] > a[maxi])
                maxi = i;
        }
        Swap(&a[begin], &a[mini]);
        //如果begin和maxi重叠，那么要修正西夏maxi的位置
        if (begin == maxi)
            maxi = mini;
        Swap(&a[end], &a[maxi]);
        ++begin;
        --end;
    }
}

直接选择排序的特性总结：

1. 直接选择排序思考非常好理解，但是效率不是很好。实际中很少使用 2. 时间复杂度： O(N^2) 3. 空间复杂度： O(1) 4. 稳定性：不稳定

5.冒泡排序

void BubbleSort(int* a, int n)
{
    assert(a);
    for (int j = 0; j < n-1; ++j)
    {
        int exchange = 0;
        for (int i = 1; i < n - j; ++i)
        {
            if (a[i - 1] > a[i])
            {
                Swap(&a[i - 1], &a[i]);
                exchange = 1;
            }
        }
        if (exchange == 0)
        {
            break;
        }
    }
}

 冒泡排序的特性总结：

1. 冒泡排序是一种非常容易理解的排序 2. 时间复杂度： O(N^2) 3. 空间复杂度： O(1) 4. 稳定性：稳定

6.快速排序

int GetMidIndex(int* a, int begin, int end)
{
    int mid = (begin + end) / 2;
    if (a[begin] < a[mid])
    {
        if (a[mid] < a[end])
        {
            return mid;
        }
        else if (a[begin] < a[end])
        {
            return end;
        }
        else
        {
            return begin;
        }
    }
    else  //a[begin]>=a[mid]
    {
        if (a[mid] > a[end])
        {
            return mid;
        }
        else if (a[begin] < a[end])
        {
            return begin;
        }
        else
        {
            return end;
        }
    }
}

int PartSort1(int* a, int begin, int end)
{
    int left = begin, right = end;
    int keyi = left;
    while (left < right)
    {
        //右边先走，找小
        while (left < right && a[right] >= a[keyi])
            --right;
        //左边再走，找大
        while (left < right && a[left] <= a[keyi])
            ++left;
        Swap(&a[left], &a[right]);
    }
    Swap(&a[keyi], &a[left]);
    keyi = left;
    return keyi;
}

//挖坑法
int PartSort2(int* a, int begin, int end)
{
    int key = a[begin];
    int piti = begin;
    while (begin < end)
    {
        //右边找小，填到左边的坑里去，这个位置形成新的坑
        while (begin < end && a[end] >= key)
            --end;
        a[piti] = a[end];
        piti = end;
        //左边找大5，填到右边的坑里去，这个位置形成新的坑
        while (begin < end && a[begin] <= key)
            ++begin;
        a[piti] = a[begin];
        piti = begin;
    }
    a[piti] = key;
    return piti;
}

//前后指针法
int PartSort3(int* a, int begin, int end)
{
    int prev = begin;
    int cur = begin + 1;
    int keyi = begin;
    //加入三数取中的优化
    int midi = GetMidIndex(a, begin, end);
    Swap(&a[keyi], &a[midi]);
    while (cur <= end)
    {
        //cur位置的值小于keyi位置的值
        if (a[cur] < a[keyi]&&++prev!=cur)
            Swap(&a[prev], &a[cur]);
        ++cur;
    }
    Swap(&a[prev], &a[keyi]);
    keyi = prev;
    return keyi;
}

void QuickSort(int* a, int begin, int end)
{
    //callCount ++;
    //区间不存在，或者只有一个值则不需要再处理
    if (begin >= end)
    {
        return;
    }

    if (end - begin > 10)
    {
        int keyi = PartSort3(a, begin, end);

        QuickSort(a, begin, keyi - 1);
        QuickSort(a, keyi + 1, end);
    }
    else
    {
        InsertSort(a+begin, end - begin + 1);
    }
}

快速排序的非递归：

void QuickSortNonR(int* a, int begin, int end)
{
    ST st;
    StackInit(&st);
    StackPush(&st, end);
    StackPush(&st, begin);
    while (!StackEmpty(&st))
    {
        int left = StackTop(&st);
        StackPop(&st);
        int right = StackTop(&st);
        StackPop(&st);
        int keyi = PartSort3(a, left, right);
        //[left,keyi-1] keyi  [keyi,right]
        if (keyi + 1 < right)
        {
            StackPush(&st, right);
            StackPush(&st, keyi + 1);
        }
        if (left < keyi - 1)
        {
            StackPush(&st, keyi - 1);
            StackPush(&st, left);
        }
    }
    StackDestroy(&st);
} 

 快速排序的特性总结：

1）时间复杂度：O(N*logN)

2） 空间复杂度：O(logN)

3）稳定性：不稳定

7.归并排序

 

void _MergeSort(int* a, int begin, int end, int* tmp)
{
    if (begin >= end)
        return;
    int mid = (begin + end) / 2;
    //[begin,mid]  [mid+1,end]  分治递归，让子区间有序
    _MergeSort(a, begin, mid, tmp);
    _MergeSort(a, mid + 1, end, tmp);
    //归并 [begin,mid]  [mid+1,end]
    int begin1 = begin, end1 = mid;
    int begin2 = mid + 1, end2 = end;
    int i = begin1;
    while (begin1 <= end1 && begin2 <= end2)
    {
        if (a[begin1] < a[begin2])
            tmp[i++] = a[begin1++];
        else
            tmp[i++] = a[begin2++];
    }
    while (begin1 <= end1)
    {
        tmp[i++] = a[begin1++];
    }
    while (begin2 <= end2)
    {
        tmp[i++] = a[begin2++];
    }
        //把归并数据拷贝回原数组
    memcpy(a + begin, tmp + begin, (end - begin + 1) * sizeof(int));
}

void MergeSort(int* a, int n)
{
    int* tmp = (int*)malloc(sizeof(int) * n);
    if (tmp == NULL)
    {
        printf("malloc failn");
        exit(-1);
    }
    _MergeSort(a, 0, n - 1, tmp);
    free(tmp);
}

归并排序的特性总结：

1. 归并的缺点在于需要 O(N) 的空间复杂度，归并排序的思考更多的是解决在磁盘中的外排序问题。 2. 时间复杂度： O(N*logN) 3. 空间复杂度： O(N) 4. 稳定性：稳定