排序算法（交换法，选择法，插入排序，冒泡法，快速排序算法，C语言举例）...

Dear 丶 2023-06-03 14:51 17阅读 0赞

***交换法：***所谓交换，就是根据序列中两个记录键值的比较结果来[对换][Link 1]这两个记录在序列中的位置，交换排序的特点是:将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动。

***简单选择排序：***的基本思想:第1趟，在待排序记录r\[1\]~r\[n\]中选出最小的记录，将它与r\[1\]交换;第2趟，在待排序记录r\[2\]~r\[n\]中选出最小的记录，将它与r\[2\]交换;以此类推，第i趟在待排序记录r\[i\]~r\[n\]中选出最小的记录，将它与r\[i\]交换，使有序序列不断增长直到全部排序完毕。

***插入排序法：***有一个已经有序的数据序列，要求在这个已经排好的数据序列中插入一个数，但要求插入后此数据序列仍然有序，这个时候就要用到一种新的排序方法--插入排序法插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据，算法适用于少量数据的排序，[时间复杂][Link 2]度为O(n^2)。是稳定的排序方法。插入算法把要排序的[数组][Link 3]分成两部分:第一部分包含了这个数组的所有元素，但将最后一个元素除外(让数组多一个空间才有插入的位置)，而第二部分就只包含这一个元素(即待插入元素)。在第一部分排序完成后，再将这个最后元素插入到已排好序的第一部分中。插入排序的基本思想是:每步将一个待排序的纪录，按其关键码值的大小插入前面已经排序的文件中适当位置上，直到全部插入完为止。

***冒泡排序：***冒泡排序（Bubble Sort，台湾译为：泡沫排序或气泡排序）是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。

以函数的形式举例

/\*交换法对数组排序\*/

void Sort(int arr[],int n)
    {
        int i, j, temp;
        for (i = 0; i < n - 1; i++)
        {
        for (j = i + 1; j < n; j++)
        {
        if (arr[j] > arr[i])/*此处降序*/
        {
    temp = arr[j];
        arr[j] = arr[i];
        arr[i] = temp;
        }
        }
        }
    }

/\*选择法对数组排序\*/

void Sort(int arr[],int n)
    {
        int i, j,k, temp;
        for (i = 0; i < n - 1; i++)
        {
        k = i;
        for (j = i + 1; j < n; j++)
        {
        if (arr[j] > arr[i])
        {
        k = j;　　　　/*记录最大值下标位置*/
        }
        }
    if (k != i)　　　　/*若最大数所在的下标位置不在位置i则进行交换*/
        {
    temp = arr[k];
        arr[k] = arr[i];
        arr[i] = temp;
        }
        }
    }

/\*冒泡法对数组排序\*/

void Sort(int arr[],int n)
    {
        int i, j, temp;
        int k = 1; /*定义k若出现有序数组则不用再判断*/
    for (i = 0; i < n - 1 && k; i++)
        {
        k = 0;
        for (j = 0; j < n - 1; j++)
        {
        if (arr[j] > arr[j + 1])
        {
        temp = arr[j];
        arr[j] = arr[i+1];
        arr[j+1] = temp;
        k = 1;
        }
        }
        }
    }

转载于:https://www.cnblogs.com/didiaoxiaoguai/p/7490383.html

[Link 1]: https://baike.so.com/doc/1077730-1140517.html
[Link 2]: https://baike.so.com/doc/107803-113805.html
[Link 3]: https://baike.so.com/doc/5545345-5760453.html