seo 发表于 2022-5-31 13:35:46

九大经典算法之插入排序、希尔排序

九大经典算法之插入排序、希尔排序发布时间：2022/5/31 12:53:46
            
                                                       
                                                       
            
      
      
               
                     
01 插入排序(Insertion Sort)
原理：每次选择一个元素，并且将这个元素和整个数组中的所有元素进行比较，然后插入到合适的位置。


void insertion_sort(int arr[], int n)
{
    int i,j;
    for (i = 1; i ) {
      int tmp = arr;
      for (j = i; j > 0 && arr > tmp; j--) {
            arr = arr;
      }
      arr = tmp;
    }
}

空间效率：O(1)

时间效率：最好情况：O(n)             平均情况：O(N^2)                     最坏情况：O(N^2)

稳定性（相同元素相对位置变化情况）：稳定

适用性：顺序存储的线性表

注：还有个折半插入排序，其原理就是查找插入位置时，从中间开始找起。

02 希尔排序（Shell Sort）
这个是插入排序的修改版，根据步长由长到短分组，进行排序，直到步长为1为止，属于插入排序的一种。


//希尔排序-希尔增量
void shell_sort(int arr[], int n) {
    int j;
    for (int d = n / 2;d > 0;d /= 2) {
      for (int i = d;i ) {
            int temp = arr;
            for (j = i;j >= d && arr > temp;j -= d)
                arr = arrj - d];
            arr = temp;
      }
    }
}


//希尔排序-sedgewick增量
void shellsedgewick_sort(int arr[], int n) {
    int i, j, d, si;
    int Sedgewick[] = { 929, 505, 209, 109, 41, 19, 5, 1, 0 };
    for (si = 0;Sedgewick >= n;si++)
      ;
    for (;Sedgewick > 0;si++) {
      d = Sedgewick;
      for (i = d;i ) {
            int temp = arr;
            for (j = i;j >= d && arr > temp;j -= d)
                arr = arr;
            arr = temp;
      }
    }
}

空间效率：O(1)

时间效率：依赖于增量序列的函数   当n在一个特定范围内时，复杂度为O(^1.3)                      最坏情况：O(N^2)

稳定性（相同元素相对位置变化情况）：不稳定

适用性：顺序存储的线性表


转载于:https://www.cnblogs.com/wanghao-boke/p/10415706.html
               
      
      
   
            
      
      
https://www.yilongzhijia.cn/tupian/seo365t.jpg
页: [1]
查看完整版本: 九大经典算法之插入排序、希尔排序