插入排序算法(直接插入排序,希尔排序)

    科技2024-11-07  13

    直接插入排序算法思想: 插入第i个数据时,前面的i-1个数据已经排好序,平均时间复杂度为O(n^2),如果找的元素和当前要插入的元素大小一致时,则插入该元素的后面,属于稳定的排序算法。 如排序序列为38 49,65,97,76,13,27,49 第一轮:38 49 待排序: 65,97,76,13,27,49 第二轮:38 49 65 待排序:97,76,13,27,49 第三轮:38 49 65 97 待排序:76,13,27,49 第四轮:38 49 65 76 97 待排序:13,27,49 第五轮:13 38 49 65 76 97 待排序:27,49 第六轮:13 27 38 49 65 76 97 待排序:49 第七轮:13 27 38 49 49 65 76 97优化后的直接插入排序算法(折半插入排序) 由于直接插入排序是边比较边移动元素,由于前面的i-1个数据是已经排好序的,因此可通过折半查找先找出要插入的位置,然后统一将元素全部后移,将比较和移动操作分离。折半插入排序是一种稳定的排序算法再优化:希尔排序(缩小增量排序) Donald Shell 从“减少记录个数”和“基本有序”这两个后面对直接插入进行了改进,提出希尔排序算法,通过将待排序记录按下标一定对增量分组(减少记录个数),对每组记录使用直接插入排序(基本有序),当增量减少至1时,整个序列基本有序,再对全部记录进行一次直接插入排序。 //插入排序: 插入第i个元素时,前面的i-1个已经排好序。 //data[0]是哨兵,哨兵避免比较后需判断查找位置是否越界,提高效率。 void InsertSortList(int data[],int length){ for (int i = 2; i <= length; i++) { data[0] = data[i]; int j = i-1; while (data[j] > data[0]) { data[j+1] = data[j]; j--; } data[j+1] = data[0]; } } //折半插入排序 void InsertBinarySort(int data[],int n){ for (int i = 2; i <= n; i++) { data[0] = data[i]; int low = 1; int high = i-1; while (low<=high) { int mid = (low + high)/2; if(data[mid] < data[0]){ low = mid + 1; }else{ high = mid - 1; } } for (int j = i-1; j >= high+1; j--) { data[j+1] = data[j]; } data[high+1] = data[0]; } } //希尔排序 //此处data[0]仅作为暂存数据,不是哨兵。 void ShellSort(int data[],int n){ for (int d = n/2 ; d >= 1; d = d/2) { for (int i = d + 1; i <= n; i++) { data[0] = data[i]; int j = i - d; while (j > 0 && data[0] < data[j]) { data[j+d] = data[j]; j = j-d; } data[j+d] = data[0]; } } }
    Processed: 0.010, SQL: 8