C语言常见的四大排序算法--插入排序、选择排序、交换排序、归并排序的实现讲解与性能对比

分类:热门推荐日期:2024-05-07浏览:1评论:0

文章目录

    • @[TOC](文章目录)
    • 前言
    • 一、排序的概念和运用
      • （一）、排序的概念
      • （二）、排序的实践运用（简单了解一下）
      • 二、插入排序
        • （一）、直接插入排序（普通版本）
        • （二）、希尔排序（缩小增量排序）
        • （三）、两个算法的时间复杂度和空间复杂度分析
        • （四）、两个算法的完整代码
        • 三、选择排序
          • （一）、直接选择排序（普通版本）
          • （二）、堆排序
          • （三）、两个算法的时间复杂度和空间复杂度分析
          • （四）、两个算法的完整代码
          • 四、交换排序
            • （一）、冒泡排序
            • （二）、快速排序
            • （三）、两个算法的时间复杂度和空间复杂度分析
            • （四）、两个算法的完整代码
            • 五、归并排序
              • （一）、 归并排序算法实现分析
              • （二）、归并排序时间复杂度和空间复杂度分析
              • （三）、归并排序代码实现
              • 六、四大排序算法性能比较
              • 总结

                前言

                本文主要介绍四大排序算法以及他们的各自的优化算法，具体优化算法有希尔算法、堆排序、快速插入排序。并求取他们的时间复杂度（这里我们实现的是升序排序）

                这里我插入两个链接版本详细介绍堆排序和快速排序（这是我以前写的两个版本）。

                一、排序的概念和运用

                （一）、排序的概念

                • 排序：所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作
                • 稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的，否则称为不稳定的。
                • 内部排序：数据元素全部放在内存中的排序
                • 外部排序：数据元素太多不能同时放在内存中，根据排序过程的要求不能再内外内存之间移动数据的排序。

                  （二）、排序的实践运用（简单了解一下）

                  二、插入排序

                  • 基本思想：把待排序的记录按其关键码值的大小逐

                    个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列 。

                    这让我联想到了扑克牌：

                    这就是典型的插入排序。

                    （一）、直接插入排序（普通版本）

                    • 直接插入排序分析：

                      这里我们先想一趟的插入排序，将大问题考虑成小问题，这里我们假设从数组下标中0到end是有序的，然后我们的小目标让0到end+1有序，这里我们就用到了while循环，每次比较a[end]与a[end+1]的大小关系，如果a[end]比tmp大的话就实行交换，然后end–，直到end回到0的位置，如果在这期间a[end]的值小于a[end+1]那么就证明已经有序了，我们可以跳出while循环了。 a[end + 1] = tmp;这句代码是我们之前提前记录了新加入比较的数据的值tmp,为了照顾如果比较到了末尾的一刻，或者在中间a[end]就比a[end+1]小，提前退出循环，我们好赋值。完成了一趟插入排序，我们只需要再写一个for循环重复多趟即可完成插入排序。

                    • 排序过程如图所示：

                      直接插入排序元素集合越接近有序，直接插入排序的算法效率越高，这个排序的稳定性较好。

                    • 代码函数展示（这里只展示局部代码后面会给出完整代码） 
                      void InsertSort(int* a, int n) {//排的升序;时间复杂度为:(最坏的情况(逆序)):1+2+3+4+...n-1
    //（最好的情况）:顺序
    for (int i = 0;i < n - 1;i++) {//end最终到n-2的数组位置，tmp到数组n-1的位置，数组下标从零开始
        int end=i;
        //[0,end]有序，插入后，[0,end+1]有序
        int tmp = a[end + 1];
        while (end >= 0)
        { if (a[end] > tmp)
            { a[end + 1] = a[end];//数据往后挪动
                end--;
            }
            else { break;
            }
        }
        a[end + 1] = tmp;//比较到末尾的一刻,或者照顾到在中间的情况:当end比tmp小的时候
    }
}

                      （二）、希尔排序（缩小增量排序）

                      • 希尔排序分析：

                        希尔排序是对插入排序的优化版本，上面我们上面插入排序的普通版本是间隔为1即a[end]和a[end+1]之间进行比较，为了加快排序效率，我们来改变相比较的间隔，来提升排序效率，这里我们定义间隔为gap,代码转换即将a[end+1]中的1换为gap即a[end+gap]其他代码跟普通版本是一样的，这里我们进行多躺排序，只需要利用while循环让gap一开始赋值为数组的大小，然后不断整除2，进行多趟排序，我们每一躺排序，都会让我们的序列更加有序，每一趟比上一躺花费的时间会更短，最终gap会变成1，即最后进行一趟普通版本的插入排序，这个会很快排好序，因为前面已经进行了多趟排序，让序列逐渐变得有序化。

                      • 排序过程如图所示：

                        希尔排序是对直接插入排序的优化；

                        当gap>1的时候都是预排序，目的是让数组更加接近有序。而当gap==1的时候，数组已经接近有序了，这样会排的很快，对整体而言，虽然排的趟数增多了，但是每趟排的时间逐渐缩短，所以最后排序效率会增加。

                      • 代码函数展示（这里只展示局部代码后面会给出完整代码）

                        void ShellSort(int* a, int n) 
{ //多组间隔为gap的预排序，gap的大小
    //把间隔为gap的数据同时排序
    //gap的取值:
    int gap=n;
    while (gap > 1)
    { gap = gap / 2;
        for (int i = 0; i < n - gap; i++)
        { int end = i;
            int tmp = a[end + gap];
            while (end >= 0)
            { if (a[end] > tmp)
                { a[end + gap] = a[end];
                    end -= gap;
                }
                else { break;
                }
            }
            a[end + gap] = tmp;
        }
    }
}

                        （三）、两个算法的时间复杂度和空间复杂度分析

                        • 直接插入排序（普通版本）：

                          时间复杂度：O(N^2)。

                          空间复杂度：O（1），这是一种稳定的排序算法。

                          稳定性：稳定。

                        • 希尔排序：

                          平均时间复杂度：O(N ^1.3——N ^2).

                          空间复杂度：O(1).

                          稳定性：不稳定

                          （四）、两个算法的完整代码

                          #include#includevoid Print(int* a, int n) { for (int i = 0; i < n; i++)
    { printf("%d ", a[i]);
    }
    printf("\n");
}
void InsertSort(int* a, int n) {//排的升序;时间复杂度为:(最坏的情况(逆序)):1+2+3+4+...n-1
    //（最好的情况）:顺序
    for (int i = 0;i < n - 1;i++) {//end最终到n-2的数组位置，tmp到数组n-1的位置
        int end=i;
        //[0,end]有序，插入后，[0,end+1]有序
        int tmp = a[end + 1];
        while (end >= 0)
        { if (a[end] > tmp)
            { a[end + 1] = a[end];//数据往后挪动
                end--;
            }
            else { break;
            }
        }
        a[end + 1] = tmp;//比较到末尾的一刻,或者照顾到在中间的情况:当end比tmp小的时候
    }
}
void ShellSort(int* a, int n) 
{ //多组间隔为gap的预排序，gap的大小
    //把间隔为gap的数据同时排序
    //gap的取值:
    int gap=n;
    while (gap > 1)
    { gap = gap / 2;
        for (int i = 0; i < n - gap; i++)
        { int end = i;
            int tmp = a[end + gap];
            while (end >= 0)
            { if (a[end] > tmp)
                { a[end + gap] = a[end];
                    end -= gap;
                }
                else { break;
                }
            }
            a[end + gap] = tmp;
        }
    }
}
void InsertSorttest()
{int a[] = { 1,9,8,6,5,44,12,33,15 };
InsertSort(a,sizeof(a) / sizeof(int));
Print(a,sizeof(a)/sizeof(int));
}
void ShellSorttest()
{ int a[] = { 1,9,8,6,5,44,12,33,15 };
 ShellSort(a, sizeof(a) / sizeof(int));
 Print(a,sizeof(a)/sizeof(int));
}
int main()
{InsertSorttest();//插入排序普通版本
ShellSorttest();//希尔排序
return 0;
}

                          三、选择排序

                          • 基本思想：每一次从待排序的数据中选出最小(或者最大)的一个元素，存放在序列的起始位置，直到全部待排序的数据元素全部排完。

                            （一）、直接选择排序（普通版本）

                            • 选择排序普通版本分析：

                              过程分析：在元素集合a[i]–a[n-1]中选择关键码最大（小）的元素；若他不是这组元素的最后一个（第一个）元素，则将她与这组元素中的最后一个（第一个）元素交换；在剩余a[i]–a[n-2]集合中，重复上述步骤，直到剩余一个元素。

                              这里我们做一个小的算法优化，在a[i]到a[n-1]个元素序列中我让关键码定为两个，一个代表最大，一个代表最小，如果最小的关键码不是第一个，则与序列的第一个元素交换，如果最大关键码不是最后一个元素，则与最后一个元素进行交换。在剩余a[i+1]到a[n-2]个元素序列中，重复以上步骤，直到集合剩余1个元素。这样会增加排序的效率

                            • 排序过程如图所示：

                              直接选择排序思考过程很简单，但是效率不是很好，实际生活中很少使用

                            • 代码函数展示（这里只展示局部代码后面会给出完整代码）

                              void Swap(int* p1, int* p2)//交换两个数的位置函数
{ int tmp = *p1;
    *p1 = *p2;
    *p2 = tmp;
}
void SelectSort(int* a, int n)//时间复杂度（O(N*N)）
{ int begin = 0;
    int end = n - 1;
    while(begin int mini = begin;
        int maxi = begin;
        for (int i = begin; i <= end; i++)
        { if (a[i] < a[mini])
            { mini = i;
            }
            if (a[i] > a[maxi])
            { maxi = i;
            }
            Swap(&a[begin], &a[mini]);
            if (begin == maxi)//避免出现bUg
            { maxi = mini;
            }
            Swap(&a[end], &a[maxi]);
        }
        begin++;
        end--;  
    }
}

                              （二）、堆排序

                              • 这里插入一个我之前写的一个版本添加链接描述

                                （三）、两个算法的时间复杂度和空间复杂度分析

                                • 直接选择排序（普通版本）：

                                  时间复杂度：O（N^2）

                                  空间复杂度：O(1)

                                • 堆排序：

                                  时间复杂度:O(N*logN)

                                  空间复杂度：O(1)

                                  （四）、两个算法的完整代码

                                  #include#includevoid Print(int* a, int n) { for (int i = 0; i < n; i++)
    { printf("%d ", a[i]);
    }
    printf("\n");
}
void Swap(int* p1, int* p2)//交换两个数的位置函数
{ int tmp = *p1;
    *p1 = *p2;
    *p2 = tmp;
}
void SelectSort(int* a, int n)//时间复杂度（O(N*N)）
{ int begin = 0;
    int end = n - 1;
    while(begin int mini = begin;
        int maxi = begin;
        for (int i = begin; i <= end; i++)
        { if (a[i] < a[mini])
            { mini = i;
            }
            if (a[i] > a[maxi])
            { maxi = i;
            }
            Swap(&a[begin], &a[mini]);
            if (begin == maxi)//避免出现bUg
            { maxi = mini;
            }
            Swap(&a[end], &a[maxi]);
        }
        begin++;
        end--;
    }
}
void AdjustDown(int* a, int n, int root)//向下调整算法,建堆
//时间复杂度：O(logN)
{ int parent = root;
    int child = parent * 2 + 1;//(左孩子的公式)
    //通过下标找出父子节点的关系
    //右孩子:rightchild=parent*2+2
    // 左孩子：leftchild=parent*2+1
    // 父亲:parent=(child-1)/2
    //孩子超过数组下标表示结束
    while (child < n)
    { if (a[child + 1] > a[child] && child + 1 < n) { ++child;
            //让child始终为左右孩子中小的那个
        }
        //小的往上浮，大的往下沉
        if (a[child] > a[parent]) { Swap(&a[child], &a[parent]);
            parent = child;
            child = parent * 2 + 1;
        }
        else { break;
        }
    }
}
void HeapSort(int* a, int n)//(时间复杂度：o(N*logN))
{ //第一步：建堆（时间复杂度为：O（n））
    //向下调整算法：前提：左右子数都是小堆
    //从根节点开始，选出左右孩子中小的哪一个，跟父亲比较，如果比父亲小就交换，然后再继续往下调，调到叶子节点就终止
    //排升序，要建大堆！！操作：第一个和最后一个交换，把他不看做堆里面。前n-1个数向下调整，选出次大的数，再跟倒数第二个位置交换
    for (int i =(n-1-1)/2 ;i >= 0;--i) {//从倒数第一个非叶子节点开始调整
        AdjustDown(a, n, i);
    }
    //第二步：//排升序，要建大堆！！操作：第一个和最后一个交换，把他不看做堆里面。前n-1个数向下调整，选出次大的数，再跟倒数第二个位置交换
    int end = n - 1;
    while (end>0)
    { Swap(&a[0], &a[end]);
        AdjustDown(a, end, 0);
        --end;
    }
}
void SelectSorttest()
{int a[] = { 3, 5, 2, 7, 8, 6, 1, 9, 4, 0 };
SelectSort(a, sizeof(a) / sizeof(int));
Print(a, sizeof(a) / sizeof(int));
}
void HeapSorttest()
{ int a[] = { 3, 5, 2, 7, 8, 6, 1, 9, 4, 0 };
 HeapSort(a, sizeof(a) / sizeof(int));
 Print(a, sizeof(a) / sizeof(int));
}
int main()
{SelectSorttest();//选择排序
HeapSorttest();//堆排序
return 0;
}

                                  四、交换排序

                                  • 基本思想：所谓交换，就是根据序列中两个记录键值得比较结果来对换这两个记录在序列中得位置，交换排序的特点就是：将键值较大的记录向序列尾部移动，键值较小的记录向序列的前部移动。

                                    （一）、冒泡排序

                                    • 冒泡排序分析：

                                      我们利用双重for循环就可以实现该排序，在外重for循环中我们遍历数组下标，在内重循环中，我们让相邻两个数进行比较，小的在前面，大的在后面，如果不是的化我们交换两个位置，直到让大的数落到后面。这样完成一趟外重for循环，紧接着进行多趟外重for循环就可以完成冒泡排序。在这里我们稍微优化了算法，我们定义一个change变量一开始赋值为零，如果在内重循环中我们只要进行了一次交换我们就让change赋值成1，经历了一趟外重循环后，如果change的值没有变，这是我们就可以退出外重循环了因为此时已经有序。

                                    • 冒泡排序的过程如图所示：

                                      冒泡排序是一种非常好理解的排序，它的稳定性较好。

                                    • 代码实现（这里只展示部分代码，后面会给出完整代码）

                                      void Swap(int* p1, int* p2)//交换两个数的位置函数
{ int tmp = *p1;
    *p1 = *p2;
    *p2 = tmp;
}
void BubbleSort(int* a, int n)
//冒泡排序（交换排序）
{ for (int i = 0; i < n; i++)
    { int change = 0;
        for (int j = 1; j  if (a[j - 1] > a[j]) { Swap(&a[j - 1], &a[j]);
                change = 1;
            }
        }
        if (change == 0)//如果冒完一遍后没有交换的现象，那么就证明有序了，后面就不需要再进行冒泡了
        { break;
        }
    }
}

                                      （二）、快速排序

                                      • 这里插入一个我之前写的一个版本添加链接描述

                                        （三）、两个算法的时间复杂度和空间复杂度分析

                                        • 冒泡排序：

                                          时间复杂度：O(N^2)

                                          空间复杂度：O(1)

                                          稳定性：稳定

                                        • 快速排序：

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

                                          空间复杂度: O(logN)~O(N)

                                          稳定性：不稳定

                                          （四）、两个算法的完整代码

                                          #include#includevoid Print(int* a, int n) { for (int i = 0; i < n; i++)
    { printf("%d ", a[i]);
    }
    printf("\n");
}
void Swap(int* p1, int* p2)//交换两个数的位置函数
{ int tmp = *p1;
    *p1 = *p2;
    *p2 = tmp;
}
void BubbleSort(int* a, int n)//冒泡排序（交换排序）
{ for (int i = 0; i < n; i++)
    { int change = 0;
        for (int j = 1; j  if (a[j - 1] > a[j]) { Swap(&a[j - 1], &a[j]);
                change = 1;
            }
        }
        if (change == 0)
        { break;
        }
    }
}
int GetMidIndex(int* a, int left, int right)//三数取中
{ int mid = (left + right) >> 1;//等效于整除于2
    if (a[left] < a[mid])
    { if (a[mid] < a[right])
        { return mid;
        }
        else if (a[left] > a[right])
        { return left;
        }
        else
        { return right;
        }
    }
    else//a[left]>=a[mid]
    { if (a[mid] > a[right])
        { return mid;
        }
        else if (a[left] < a[right])
        { return left;
        }
        else
        { return right;
        }
    }
}
//利用挖洞法来进行快速排序
int Part1Sort(int* a, int left, int right)//实现分治递归//时间复杂度：O（N*log(N))
{ //三数取中法，如果一开始为有序时候，为了降低时间复杂度(将begin赋予整体数据较为靠中数据的下标值)
    int index = GetMidIndex(a, left, right);
    Swap(&a[left], &a[index]);
    //第一趟排序：
    int begin = left, end = right;
    int pivot = begin;//让洞的位置为最开始位置
    int key = a[begin];
    while (begin < end)
    { //从最右面开始找比key小的数，放到左面
        while (begin < end && a[end] >= key)//注意begin=key要加上等于防止出现死循环BUG
        { --end;
        }
        //小的数据放在左边的坑位，自己的位置形成新的坑位
        a[pivot] = a[end];
        pivot = end;
        //从最左面开始找比key大的数，放在右面
        while (begin < end && a[begin] <= key)
        { ++begin;
        }
        //大的数据放在右边的坑位，自己的位置形成新的坑位
        a[pivot] = a[begin];
        pivot = begin;
    }
    //最后将begin或者end(此两者相等)赋给洞，此时洞的位置即key值自己真实的大小位置
    pivot = begin;
    a[pivot] = key;
    //此时再让左子区间和右子区间分别有序，那么最终就有序了
    //实现方法：分治递归：}
    return pivot;
}
//左右指针法来实现快速排序
int Part2Sort(int* a, int left, int right)//左右指针法来进行快速排序
{ int index = GetMidIndex(a, left, right);
    Swap(&a[left], &a[index]);
    int begin = left, end = right;
    int keyi = begin;
    while (begin < end)
    { //从右边开始找比a[keyi]小的数据
        while (begin < end && a[end] >= a[keyi])
        { --end;
        }
        //从左边开始找比a[keyi]大的数据
        while (begin < end && a[begin] <= a[keyi])
        { ++begin;
        }
        //从两边分别找到比a[keyi]小的数据和比a[keyi]大的数据，将两数据进行交换
        Swap(&a[begin], &a[end]);
    }
    //将a[keyi]于a[begin]交换或者于a[end]交换，将a[keyi]放在真实大小的位置
    Swap(&a[begin], &a[keyi]);
    return begin;
}
int Part3Sort(int* a, int left, int right)//前后指针法来进行快速排序
{ int index = GetMidIndex(a, left, right);
    Swap(&a[left], &a[index]);
    int keyi = left;
    int prev = left, cur = left + 1;
    //cur找比a[keyi]小的数，每次遇到比key小的值就停下来，++prev,交换prev和cur位置的值
    while (cur<=right)
    { if (a[cur] < a[keyi]&&++prev !=cur)//这里不需要等于，不会出现死循环的BUG
        { Swap(&a[prev], &a[cur]);
        }
        ++cur;
    }
    Swap(&a[keyi], &a[prev]);
    return prev;
}
void QuickSort(int* a, int left, int right)//实现分治递归//时间复杂度：O（N*log(N))
{ if (left >= right)
    { return;
    }
    //将左子区间和右子区间变为有序，实现方法：分治递归；
    int keyIndex = Part3Sort(a, left, right);//上面三种方法选择其一即可
    QuickSort(a, left, keyIndex - 1);
    QuickSort(a, keyIndex + 1, right);
}
void BubbleSorttest()
{ int a[] = { 3, 5, 2, 7, 8, 6, 1, 9, 4, 0 };
 BubbleSort(a, sizeof(a) / sizeof(int));
 Print(a, sizeof(a) / sizeof(int));
}
void QuicktSorttest()
{int a[] = { 3, 5, 2, 7, 8, 6, 1, 9, 4, 0 };
QuickSort(a, 0, sizeof(a) / sizeof(int)-1);
Print(a, sizeof(a) / sizeof(int));
}
int main()
{BubbleSorttest();//冒泡排序
QuicktSorttest();//快速排序
return 0;
}

                                          五、归并排序

                                          （一）、 归并排序算法实现分析

                                          • 基本思想：归并排序是建立在归并操作上的一种有效的排序算法，该算法是采用分治递归的一种非常典型的应用，将已有序列的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，则称为二路归并。
                                          • 归并过程如图所示：

                                            这里提一点：归并的缺点在于要使用O(N)的空间复杂度，归并排序的思考更多的是解决磁盘中的外排序问题。

                                            （二）、归并排序时间复杂度和空间复杂度分析

                                            • 时间复杂度：O(N*logN)
                                            • 空间复杂度：O(N)
                                            • 稳定性：稳定

                                              （三）、归并排序代码实现

                                              #include#includevoid Print(int* a, int n) {//打印一下数组
    for (int i = 0; i < n; i++)
    { printf("%d ", a[i]);
    }
    printf("\n");
}
void _MergeSort(int* a, int left, int right, int* tmp)
{ if (left >= right)//递归的限制条件
    { return;
    }
    int mid = (left + right) >> 1;//取得中间数字
    _MergeSort(a, left, mid, tmp);//让左区间有序
    _MergeSort(a, mid + 1, right, tmp);//让右区间有序
    int begin1 = left;
    int end1 = mid;
    int begin2 = mid + 1;
    int end2 = right;
    int index = left;
    while (begin1<=end1&&begin2<=end2)
    { if (a[begin1] < a[begin2])
        { tmp[index++] = a[begin1++];
        }
        else
        { tmp[index++] = a[begin2++];
        }
    }
    while (begin1 <= end1)
    { tmp[index++] = a[begin1++];
    }
    while (begin2 <= end2)
    { tmp[index++] = a[begin2++];
    }
    //拷贝回去
    for (size_t i = left; i <= right; i++)
    { a[i] = tmp[i];
    }
}
void MergeSort(int* a, int n)
{ int left = 0;
    int right = n - 1;
    int* tmp = (int*)malloc(sizeof(int) * n);//开辟新空间数组
    _MergeSort(a, left, right, tmp);
    free(tmp);//释放数组
}
int main() 
{int a[] = { 3, 5, 2, 7, 8, 6, 1, 9, 4, 0 };
MergeSort(a, sizeof(a) / sizeof(int));
Print(a, sizeof(a) / sizeof(int));
}

                                              六、四大排序算法性能比较

                                              • 上面提到的7中排序复杂度及稳定性汇总分析：

                                                如图所示：

                                                • 接下来我们利用代码来进行它们之间的性能比较：
                                                • 代码实现： 
                                                  #include#includevoid Print(int* a, int n) { for (int i = 0; i < n; i++)
    { printf("%d ", a[i]);
    }
    printf("\n");
}
void InsertSort(int* a, int n) {//排的升序;时间复杂度为:(最坏的情况(逆序)):1+2+3+4+...n-1
    //（最好的情况）:顺序
    for (int i = 0;i < n - 1;i++) {//end最终到n-2的数组位置，tmp到数组n-1的位置
        int end=i;
        //[0,end]有序，插入后，[0,end+1]有序
        int tmp = a[end + 1];
        while (end >= 0)
        { if (a[end] > tmp)
            { a[end + 1] = a[end];//数据往后挪动
                end--;
            }
            else { break;
            }
        }
        a[end + 1] = tmp;//比较到末尾的一刻,或者照顾到在中间的情况:当end比tmp小的时候
    }
}
void ShellSort(int* a, int n) 
{ //多组间隔为gap的预排序，gap的大小
    //把间隔为gap的数据同时排序
    //gap的取值:
    int gap=n;
    while (gap > 1)
    { gap = gap / 2;
        for (int i = 0; i < n - gap; i++)
        { int end = i;
            int tmp = a[end + gap];
            while (end >= 0)
            { if (a[end] > tmp)
                { a[end + gap] = a[end];
                    end -= gap;
                }
                else { break;
                }
            }
            a[end + gap] = tmp;
        }
    }
  
}
void Swap(int* p1, int* p2)//交换两个数的位置函数
{ int tmp = *p1;
    *p1 = *p2;
    *p2 = tmp;
}
void SelectSort(int* a, int n)//时间复杂度（O(N*N)）
{ int begin = 0;
    int end = n - 1;
    while(begin int mini = begin;
        int maxi = begin;
        for (int i = begin; i <= end; i++)
        { if (a[i] < a[mini])
            { mini = i;
            }
            if (a[i] > a[maxi])
            { maxi = i;
            }
            Swap(&a[begin], &a[mini]);
            if (begin == maxi)//避免出现bUg
            { maxi = mini;
            }
            Swap(&a[end], &a[maxi]);
        }
        begin++;
        end--;
       
    }

}
void AdjustDown(int* a, int n, int root)//向下调整算法,建堆
//时间复杂度：O(logN)
{ int parent = root;
    int child = parent * 2 + 1;//(左孩子的公式)
    //通过下标找出父子节点的关系
    //右孩子:rightchild=parent*2+2
    // 左孩子：leftchild=parent*2+1
    // 父亲:parent=(child-1)/2
    //孩子超过数组下标表示结束
    while (child < n)
    { if (a[child + 1] > a[child] && child + 1 < n) { ++child;
            //让child始终为左右孩子中小的那个
        }
        //小的往上浮，大的往下沉
        if (a[child] > a[parent]) { Swap(&a[child], &a[parent]);
            parent = child;
            child = parent * 2 + 1;
        }
        else { break;
        }
    }
    
}
void HeapSort(int* a, int n)//(时间复杂度：o(N*logN))
{ //第一步：建堆（时间复杂度为：O（n））
    //向下调整算法：前提：左右子数都是小堆
    //从根节点开始，选出左右孩子中小的哪一个，跟父亲比较，如果比父亲小就交换，然后再继续往下调，调到叶子节点就终止
    //排升序，要建大堆！！操作：第一个和最后一个交换，把他不看做堆里面。前n-1个数向下调整，选出次大的数，再跟倒数第二个位置交换
    for (int i =(n-1-1)/2 ;i >= 0;--i) {//从倒数第一个非叶子节点开始调整
        AdjustDown(a, n, i);
    }
    //第二步：//排升序，要建大堆！！操作：第一个和最后一个交换，把他不看做堆里面。前n-1个数向下调整，选出次大的数，再跟倒数第二个位置交换
    int end = n - 1;
    while (end>0)
    { Swap(&a[0], &a[end]);
        AdjustDown(a, end, 0);
        --end;
    }
}
void BubbleSort(int* a, int n)
//冒泡排序（交换排序）
{ for (int i = 0; i < n; i++)
    { int change = 0;
        for (int j = 1; j  if (a[j - 1] > a[j]) { Swap(&a[j - 1], &a[j]);
                change = 1;
            }
        }
        if (change == 0)
        { break;
        }
    }
}
int GetMidIndex(int* a, int left, int right)
{ int mid = (left + right) >> 1;//等效于整除于2
    if (a[left] < a[mid])
    { if (a[mid] < a[right])
        { return mid;
        }
        else if (a[left] > a[right])
        { return left;
        }
        else
        { return right;
        }
    }
    else//a[left]>=a[mid]
    { if (a[mid] > a[right])
        { return mid;
        }
        else if (a[left] < a[right])
        { return left;
        }
        else
        { return right;
        }
    }
}
//利用挖洞法来进行快速排序
int Part1Sort(int* a, int left, int right)//实现分治递归//时间复杂度：O（N*log(N))
{ //三数取中法，如果一开始为有序时候，为了降低时间复杂度(将begin赋予整体数据较为靠中数据的下标值)
    int index = GetMidIndex(a, left, right);
    Swap(&a[left], &a[index]);
    //第一趟排序：
    int begin = left, end = right;
    int pivot = begin;//让洞的位置为最开始位置
    int key = a[begin];
    while (begin < end)
    { //从最右面开始找比key小的数，放到左面
        while (begin < end && a[end] >= key)//注意begin=key要加上等于防止出现死循环BUG
        { --end;
        }
        //小的数据放在左边的坑位，自己的位置形成新的坑位
        a[pivot] = a[end];
        pivot = end;
        //从最左面开始找比key大的数，放在右面
        while (begin < end && a[begin] <= key)
        { ++begin;
        }
        //大的数据放在右边的坑位，自己的位置形成新的坑位
        a[pivot] = a[begin];
        pivot = begin;
    }
    //最后将begin或者end(此两者相等)赋给洞，此时洞的位置即key值自己真实的大小位置
    pivot = begin;
    a[pivot] = key;
    //此时再让左子区间和右子区间分别有序，那么最终就有序了
    //实现方法：分治递归：}
    return pivot;
}
//左右指针法来实现快速排序
int Part2Sort(int* a, int left, int right)//左右指针法来进行快速排序
{ int index = GetMidIndex(a, left, right);
    Swap(&a[left], &a[index]);
    int begin = left, end = right;
    int keyi = begin;
    while (begin < end)
    { //从右边开始找比a[keyi]小的数据
        while (begin < end && a[end] >= a[keyi])
        { --end;
        }
        //从左边开始找比a[keyi]大的数据
        while (begin < end && a[begin] <= a[keyi])
        { ++begin;
        }
        //从两边分别找到比a[keyi]小的数据和比a[keyi]大的数据，将两数据进行交换
        Swap(&a[begin], &a[end]);
    }
    //将a[keyi]于a[begin]交换或者于a[end]交换，将a[keyi]放在真实大小的位置
    Swap(&a[begin], &a[keyi]);
    return begin;
}
int Part3Sort(int* a, int left, int right)//前后指针法来进行快速排序
{ int index = GetMidIndex(a, left, right);
    Swap(&a[left], &a[index]);
    int keyi = left;
    int prev = left, cur = left + 1;
    //cur找比a[keyi]小的数，每次遇到比key小的值就停下来，++prev,交换prev和cur位置的值
    while (cur<=right)
    { if (a[cur] < a[keyi]&&++prev !=cur)//这里不需要等于，不会出现死循环的BUG
        { Swap(&a[prev], &a[cur]);
        }
        ++cur;
    }
    Swap(&a[keyi], &a[prev]);
    return prev;
}
void QuickSort(int* a, int left, int right)//实现分治递归//时间复杂度：O（N*log(N))
{ if (left >= right)
    { return;
    }
    //将左子区间和右子区间变为有序，实现方法：分治递归；
    int keyIndex = Part3Sort(a, left, right);
    QuickSort(a, left, keyIndex - 1);
    QuickSort(a, keyIndex + 1, right);
}
void _MergeSort(int* a, int left, int right, int* tmp)
{ if (left >= right)
    { return;
    }
    int mid = (left + right) >> 1;//取得中间数字
    _MergeSort(a, left, mid, tmp);//让左区间有序
    _MergeSort(a, mid + 1, right, tmp);//让右区间有序
    int begin1 = left;
    int end1 = mid;
    int begin2 = mid + 1;
    int end2 = right;
    int index = left;
    while (begin1<=end1&&begin2<=end2)
    { if (a[begin1] < a[begin2])
        { tmp[index++] = a[begin1++];
        }
        else
        { tmp[index++] = a[begin2++];
        }
    }
    while (begin1 <= end1)
    { tmp[index++] = a[begin1++];
    }
    while (begin2 <= end2)
    { tmp[index++] = a[begin2++];
    }
    //拷贝回去
    for (size_t i = left; i <= right; i++)
    { a[i] = tmp[i];
    }
}
void MergeSort(int* a, int n)
{ int left = 0;
    int right = n - 1;
    int* tmp = (int*)malloc(sizeof(int) * n);
    _MergeSort(a, left, right, tmp);
    free(tmp);
}
void testOP()
{srand(time(0));
const int N = 100000;
int* a1 = (int*)malloc(sizeof(int) * N);
int* a2 = (int*)malloc(sizeof(int) * N);
int* a3 = (int*)malloc(sizeof(int) * N);
int* a4 = (int*)malloc(sizeof(int) * N);
int* a5 = (int*)malloc(sizeof(int) * N);
int* a6 = (int*)malloc(sizeof(int) * N);
for (int i = 0; i < N; ++i)
{a1[i] = rand();
	a2[i] = a1[i];
	a3[i] = a1[i];
	a4[i] = a1[i];
	a5[i] = a1[i];
	a6[i] = a1[i];
}
int begin1 = clock();
InsertSort(a1, N);
int end1 = clock();
int begin2 = clock();
ShellSort(a2, N);
int end2 = clock();
int begin3 = clock();
SelectSort(a3, N);
int end3 = clock();
int begin4 = clock();
HeapSort(a4, N);
int end4 = clock();
int begin5 = clock();
QuickSort(a5, 0, N - 1);
int end5 = clock();
int begin6 = clock();
MergeSort(a6, N);
int end6 = clock();
printf("InsertSort:%d\n", end1 - begin1);
printf("ShellSort:%d\n", end2 - begin2);
printf("SelectSort:%d\n", end3 - begin3);
printf("HeapSort:%d\n", end4 - begin4);
printf("QuickSort:%d\n", end5 - begin5);
printf("MergeSort:%d\n", end6 - begin6);
free(a1);
free(a2);
free(a3);
free(a4);
free(a5);
free(a6);
}
int main()
{testOP();
}
                                                  • 结果显示：

                                                    这里我们给出100000个随机数字进行排序，通过运行的毫秒数来显示排序算法的效率高低，可以明显的看出直接插入排序的普通版本和选择排序的效率和性能是比较低的，而快排和归并排序的效率和性能是比较高的。堆排序和希尔排序效率也是比较高的。我们根据运行时间长短来衡量效率的高低。

                                                    总结

                                                    本文详细介绍了四大排序–插入排序（直接插入排序，希尔排序）、选择排序（直接选择排序，堆排序）、交换排序（冒泡排序，快速排序）的实现过程，以及它们的性能比较。代码都是我亲自打出来的，都已检验没问题，大家可以放心使用，如有错误，请批评指正，请大家多多支持。

相关推荐

关于我们常见问题广告服务免责声明联系我们
Powered By Z-BlogPHP 1.7.3 Theme By 优美主题
Copyright Your WebSite.Some Rights Reserved. 浙ICP备2023018783号