【算法】排序算法总结

内排序

一、插入排序

插入排序包括：直接插入排序和希尔排序

1.1 直接插入排序

算法思想：

直接插入排序是一种简单的插入排序法，其基本思想是把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列。

用一个形象的比喻：摸牌与插牌。

下面进行动图演示

算法的代码实现

void insert_sort(int a[], int n)
{
   
    // tmp表示要插入的元素
    // end表示已插入元素最后一个元素的下标
    int tmp, end;
    // 1个元素默认有序，因此从1开始
    for (int i = 1; i < n; i++)
    {
   
        tmp = a[i];
        end = i - 1;
        while (end >= 0)
        {
   
            // 1. 如果a[end] > tmp， 则a[end]向后移, end--
            // 如果a[end] <= tmp，则a[end+1] = tmp
            // 特殊情况：如果tmp是最小的数，则end = -1会跳出循环，因此在循环体外赋值
            if (a[end] > tmp)
            {
   
                a[end + 1] = a[end];
                end--;
            }
            else
            {
   
                break;
            }
        }
        a[end + 1] = tmp;
    }
}

算法评价：

1. 元素集合越接近有序，直接插入排序算法的时间效率越高

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

3. 空间复杂度：O(1)，它是一种稳定的排序算法

4. 稳定性：稳定

改进：插入排序效率的重点：减少比较的次数，如何减少比较的次数？2的方向

1. 快速定位新插入的元素在已排序好的位置 --> 折半查找

2. 让原来的序列趋近于有序 --> 希尔排序

1.2 折半插入排序

算法思想

直接插入排序中将无序区的开头元素Ri插入到有序区 R[0…i-1]是采用顺序比较的方法。由于有序区的元素是有序的,可以采用折半查找方法先在R0…i-1中找到插入位置,再通过移动元素进行插入,这样的插入排序称为折半插入排序(binary insertion sort)或二分插人排序

算法实现

void mid_insert_sort(int a[], int n)
{
   
    int tmp, end;
    for(int i = 1; i < n; i++)
    {
   
        tmp = a[i];
        end = i-1;
        // 1. 折半查找位置 -- 注意稳定性，令 <= 为l区域
        int l = -1, r = i;
        while(l+1 != r)
        {
   
            int mid = l + r >> 1;
            if(a[mid] > tmp) r = mid;
            else l = mid;
        }
        // 2. 后移元素，[0 l] [r i-1], l+1的地方插入，后移[l+1, i-1]一位
        while(end >= l+1)
        {
   
            a[end+1] = a[end];
            --end; 
        }
        a[l+1] = tmp;
    }
}

算法评价

折半插入排序的元素移动次数与直接插入排序相同,不同的仅是变分散移动为集中移动。在R0…i-1中查找插入R[]的位置,折半查找的平均关键字比较次数约为log(i+1)-1,平均移动元素的次数为i/2+2,所以平均时间复杂度为:

实际上,折半插入排序和直接插入排序相比移动元素的性能没有改善,仅仅减少了关键字的比较次数。就平均性能而言,由于折半查找优于顺序查找,所以折半插入排序也优于直接插入排序。折半插入排序的空间复杂度为(1),也是一种稳定的排序方法。

1.3 希尔排序

算法思想

希尔排序法又称缩小增量法。希尔排序法的基本思想是：先选定一个整数gap，把待排序文件中所有数据分成gap个组，所有距离为gap的数据分在同一组内，并对每一组内的数据进行排序。然后，取 gap = gap/2，重复上述分组和排序的工作。当到达gap=1时，数据将排好序.

算法实现

//单组排完，在排下一组
void shell_sort(int a[], int n)
{
   
    int gap = n;
    while (gap > 1)
    {
   
        gap /= 2;
        //gap /= 3 + 1;
        //1. 分组
        for (int i = 0; i < gap; i++)
        {
   
            // 2. 单组插入排序
            int tmp, end;
            for (int j = i+gap; j < n; j += gap)
            {
   
                tmp = a[j];
                end = j - gap;
                while (end >= i)
                {
   
                    if (a[end] > tmp)
                    {
   
                        a[end + gap] = a[end];
                        end -= gap;
                    }
                    else break;
                }
                a[end+gap] = tmp;
            }
        }
    }
}
//多组并行
void shell_sort(int a[], int n)
{
   
    int gap = n;
    while (gap > 1)
    {
   
        gap /= 2;
        //多组并行
        for (int i = 0; i + gap < n; i++)
        {
   
            int tmp = a[i + gap];
            int end = i;
            while (end >= 0)
            {
   
                if (a[end] > tmp)
                {
   
                    a[end + gap] = a[end];
                    end -= gap;
                }
                else break;
            }
            a[end + gap] = tmp;
        }
    }
}

算法评价

希尔排序的空间复杂度：O(1)

希尔排序的时间复杂度：


希尔排序法是一种不稳定的排序算法。例如,若希尔排序分为{3,10,7,8,20}和(5,8,2,1,6)两组,显然第1组的8排列在第2组的8的后面,两组采用直接插入排序后的结果为(3,7,8,10,20}和{1,2,5,6,8),这样第1组的8排列到第2组的8的前面,它们的相对位置发生了改变。

二、选择排序

2.1 简单选择排序

算法思想

每次从剩余数中选出最小的数，与已排序的数组后面一个元素换位置

算法实现

//原版 -- 每次选出最小
void select_sort(int a[], int n)
{
   
    for (int i = 0; i < n; i++)
    {
   
        int Min_i = i;
        // 1. 单趟找最小元素的下标
        for (int j = i; j < n; j++)
        {
   
            if (a[Min_i] > a[j])
            {
   
                Min_i = j;
            }
        }
        // 2. 与i下标对应的元素交换
        std::swap(a[Min_i], a[i]);
    }
}
//优化版 -- 每次选出最大和最小
void select_sort(int a[], int n)
{
   
    int l = 0, r = n - 1;
    while(l < r)
    {
   
        int Min_i = l, Max_i = r;
        // 1. 单趟找最小和最大元素的下标
        for (int j = l; j <= r; j++)
        {
   
            if (a[Min_i] > a[j])
            {
   
                Min_i = j;
            }
            if (a[Max_i] < a[j])
            {
   
                Max_i = j;
            }
        }
        // 2. 与l，r下标对应的元素交换
        std::swap(a[Min_i], a[l]);
        //存在情况：l指向的数就是目前区间的最大值
        if (l