排序算法-综述

1、冒泡排序算法：

冒泡排序算法是最简单也是最基本的排序算法之一，算法的原理为如下：

原理：将数据当中的每一个元素与之后的元素进行对比，如果当前元素比序列后的元素的值小，则交换两者的顺序，依次类推，直到最后一个数据完成排序即可！

时间复杂度：O(n2)

API实现如下(两层for循环嵌套实现)：

复制

int BubbleSort(int *In, int N)

{

    int temp;

    for (int i = 0; i < N; i++) {

        for (int j = i + 1; j < N; j++) {

            if (In[i] > In[j]) {

                temp = In[i];

                In[i] = In[j];

                In[j] = temp;

            }

        }

    }

    return 1;

}

2、插入排序算法：

插入排序算法是最基本的排序算法之一，少量数据的排序，其效率较高，算法的原理为如下：

原理：从第一个数值开始排序，在每一个P循环之后，0-P之间的所有元素都是已经完成排序了，P之后的第一个数据作为插值，和前面的顺序序列对比并插入正确的位置！

时间复杂度：O(n2)，对于基本排列好序列的数据，插入排序算法的时间复杂度为O(n)。

API实现如下：

复制

int InsertSort(int *In, int N)

{

    int P, i, temp;

    for (P = 1; P < N; P++) {

        temp = In[P];

        for (i = P; i > 0 && temp < In[i - 1]; i--) {

            In[i] = In[i - 1];

        }

        In[i] = temp;

    }

    return 1;

}

3、希尔排序算法：

希尔排序算法的平均时间复杂度较低，算法的原理如下：

原理：算法在运行的过程中，每次将前面的数据与其间隔stride步长位置的数据进行对比，完成当前stride的全部对比之后，将stride缩小为原来的一半，以此类推，最后stride为1，这个时候对比的就是相邻的元素，对比完成，序列同时完成了排序。

时间复杂度：O(n*log(n))

API_0实现如下(常规的希尔序列初始增量：N/2. N为数据的长度)：

复制

int ShellSort(int *In, int N)

{

    int i, j, stride,Temp;

    /* 这里需要注意的是，stride最终的结果为0：当stride=1时，stride/=2得到的stride=floor(0.5)=0,所以循环退出 */

    for (stride = N / 2; stride > 0; stride /= 2) {

        for (i = stride; i < N; i++) {

            Temp = In[i];

            for (j = i; j >= stride && Temp < In[j - stride] ; j -= stride) {

                    In[j] = In[j - stride];

            }

            In[j] = Temp;

        }

    }

    return 1;

}

API_1实现如下(希尔Hibbard增量序列：Hibbard：{1, 3, ..., 2^k-1})

注：这是一种冲破二次时间屏障的算法

复制

int ShellSort_Hibbard(int *In, int N) // 时间复杂度最坏的情况为o(N^3/2)

{

    int i, j, stride, Temp;

    int k = log2(N / 2 + 1);

    // printf("The k is:%d\n", k);

    /* 这里需要注意的是，stride最终的结果为0：当stride=1时，stride/=2得到的stride=floor(0.5)=0,所以循环退出 */

    for (stride = (2<<k) - 1; stride > 0 && k >= 1; stride = (1<<k) - 1) { // 注意这里的左移运算的优先级低于减法的优先级，所以要打上括号

        // printf("The stride is:%d\n", stride);

        for (i = stride; i < N; i++) {

            Temp = In[i];

            for (j = i; j >= stride && Temp < In[j - stride]; j -= stride) {

                In[j] = In[j - stride];

            }

            In[j] = Temp;

        }

        k -= 1;

    }

    return 1;

}

4、选择快速排序算法：

快速排序算法的平均时间复杂度低，比较适合大量数据的排序算法，算法的原理如下：

原理：快速排序算法的情况和归并排序算法比较相似！详细原理参考这里：https://www.jianshu.com/p/7631d95fdb0b

时间复杂度：O(n*log(n))

API实现如下：

复制

#define Cutoff 3

void Swap(int *A, int *B)

{

    int Temp;

    Temp = *A;

    *A = *B;

    *B = Temp;

}

int Median3(int A[], int left, int right) // 寻找枢纽值

{

    int center = (left + right) / 2;

    int Temp;



    if (A[left] > A[center])

        Swap(&A[left], &A[center]);

    if (A[left] > A[right])

        Swap(&A[left], &A[right]);

    if (A[center] > A[right])

        Swap(&A[center], &A[right]);



    Swap(&A[center], &A[right - 1]); // 将枢纽值保存在数组的边缘

    return A[right - 1];  // return pivot-返回枢纽值

}

void QSort(int A[], int left, int right)

{

    int i, j;

    int pivo;

    if (left + Cutoff <= right) { // 小数组的处理交给插值排序的方法，速度比较快一些

        pivo = Median3(A, left, right); // 枢纽值求解

        i = left; j = right - 1;

        for (;;)

        {

            while (A[++i] < pivo) { } // 分割策略

            while (A[--j] > pivo) { } // 分割策略

            if (i < j)

                Swap(&A[i], &A[j]);

            else

                break;

        }

        Swap(&A[i], &A[right - 1]); // Swap函数属于外部调用，为了提高算法的效率可以直接显式写出代码，不用callSwap函数



        QSort(A, left, i-1); // 分割之后的递归调用

        QSort(A, i+1, right); // 分割之后的递归调用

    }

    else {

        InsertSort(A + left, right - left + 1); // 插值排序算法

    }



}

void QuickSort(int A[], int N)

{

    QSort(A, 0, N-1);

}

5、堆排序算法：

堆排序算法的平均时间复杂度较低，算法的原理如下：

原理：堆排序算法主要使用了堆数据结构的特点，创建二叉堆，并进行堆排序，即可完成数据的排序。

时间复杂度：O(n*log(n))

API实现如下：

复制

#define LeftChild(i) (2*(i)+1)

void PerDown(int A[], int i, int N) // 降过滤法完成二叉堆的生成

{

    int Child;

    int Tmp;

    for (Tmp = A[i]; LeftChild(i) < N; i = Child) {

        Child = LeftChild(i);

        if (Child != N - 1 && A[Child + 1] > A[Child])

            Child++;

        if (Tmp < A[Child])

            A[i] = A[Child];

        else

            break;

    }

    A[i] = Tmp;

}

void Swap(int *A, int *B)

{

    int Temp;

    Temp = *A;

    *A = *B;

    *B = Temp;

}

void HeapSort(int A[], int N)

{

    int i;

    for (i = N / 2; i >= 0; i--) {

        PerDown(A, i, N); // 创建二叉堆

    }

    for (i = N - 1; i > 0; i--)

    {

        Swap(&A[0], &A[i]); // Delet the Max Element

        PerDown(A, 0, i);

    }

}

6、桶排序算法：

堆排序算法的平均时间复杂度较低，算法的原理如下：

原理：桶排序算法主要使用了类似于散列表的特点，将待排序的数据的数据内容统计起来，按照index桶的位置来确保数据的顺序问题，从而完成了桶排序的任务！

时间复杂度：O(n)

API实现如下：

复制

void BucketSort(int A[], int N, int MAX) // 对于排序小整数的情况，buckect桶排序算法非常的适合

{

    int *Bucket = (int *)malloc(sizeof(int)*MAX);

    int index;

    for (int i = 0; i < MAX; i++) {

        *(Bucket + i) = 0;

    }

    for (int i = 0; i < N; i++) {

        index = A[i];

        Bucket[index] += 1;

    }

    index = 0;

    for (int i = 0; i < MAX; i++) {

        while (Bucket[i] != 0) {

            A[index] = i;

            index += 1;

            Bucket[i] -= 1;

        }

    }

}

支持下，谢谢分享！