排序算法哪种好?

发布网友发布时间：2024-01-16 22:02

共1个回答

热心网友时间：2024-05-13 03:43

在插入和选择排序中，若初始数据基本正序，则选用插入排序；若初始数据基本反序，则选用选择排序。

插入排序基本思想：

输入一个元素，插入到一个已经排好序的数列中的适当位置，使数列依然有序。

例如：输入一个数，插入一个各元素已经按照升序排列的数组中，插入后使数组中元素仍然是按照升序排列的。思想：把欲插入的数与数组中各数逐个比较，当找到第一个比插入数大的元素i时，该元素之前即为插入位置。

然后从数组最后一个元素开始到该元素为止，逐个后移一个单元。最后把插入数赋予元素a[i]即可。如果被插入数比所有的元素值都小则插入最后位置。

扩展资料：

插入排序对于随机排列长度为N的且主键不重复的数组，平均情况下插入排序需要~(N^2)/4次比较以及~(N^2)/4次交换。最坏情况下需要~(N^2)/2次比较和~(N^2)/2次交换，最好情况下需要N-1次比较和0次交换。

插入排序需要的交换操作和数组中倒置的数量相同，需要的比较次数大于等于倒置的数量，小于等于倒置的数量加上数组的大小再减一。

要大幅提高插入排序的速度并不难，只要在内循环中将较大的元素都向右移动而不总是交换两个元素（这样访问数组的次数就能减半）