插入排序(Insertion Sort)
Acx7 人气:0介绍：
直接插人排序的工作方式像许多人排序一手扑克牌。开始时，我们的左手为空并且桌子上的牌面向下。然后，我们每次从桌子上拿走一张牌并将它插入左手中正确的位置。为了找到一张牌的正确位置,我们从右到左将它与已在手中的每张牌进行比较。如图2-1所示，拿在左手上的牌总是排序好的,原来这些牌是桌子上牌堆中顶部的牌。对于少量元素的排序，插入排序是一个有效的算法。
思想：
首先我们将数组中的数据分为两个区间，已排序区间和未排序区间。初始已排序区间只有一个元素，就是数组的第一个元素，然后在未排序区间中依次取出元素并插入到已排序区间的合适位置，并保证已排序区间一直是有序。重复这个步骤直到未排序区间元素为空，排序完成。
性能分析：
时间复杂度：O(N^2)
空间复杂度：O(1)
稳定性：稳定
代码实现：
// Java代码
class StraighInsertionSort {
public static void straightInsertionSort(int[] array) {
for (int i = 1; i < array.length; ++i) {// 遍历无序序列
int key = array[i];// 记录准备插入的元素
int j = i - 1;// 记录当前比较位置指针
while (j >= 0 && array[j] > key) {// 寻找插入位置
array[j + 1] = array[j];// 元素后移
--j;// 指针减1，当前比较位置前移
}
array[j + 1] = key;// 插入合适位置
}
}
}
// C++代码
class StraightInsertionSort {
public:
static void straightInsertionSort(int array[], int length) {
for (int i = 1; i < length; ++i) {// 遍历无序序列
int key = array[i];// 记录准备插入的元素
int j = i - 1;// 记录当前比较位置指针
while (j >= 0 && array[j] > key) {// 寻找插入位置
array[j + 1] = array[j];// 元素后移
--j;// 指针减1，当前比较位置前移
}
array[j + 1] = key;// 插入合适位置
}
}
};
算法优化：
上面的代码在有序序列中查找时采用顺序查找，既然是有序序列，自然可以想到采用二分查找减少查找次数。时间复杂度还是 O(N^2)，因为不管是二分查找还是顺序查找，大部分时间都花在遍历和元素的后移上，二分查找只能在查找位置上节约时间。
// Java代码
class BinaryInsertionSort {
public static void binaryInsertionSort(int[] array) {
for (int i = 1; i < array.length; ++i) {// 遍历无序序列
int left = 0;// 有序序列左指针
int right = i - 1;// 有序序列右指针
int key = array[i];// 记录准备插入的元素
while (left <= right) {
int mid = (left + right) / 2;// 有序序列中间位置
if (array[mid] < key) {// 二分查找
left = mid + 1;
} else {// array[mid] >= key两种情况合并，便于后续统一处理
right = mid - 1;
}
}
// 找到元素插入位置后，整体后移
for (int j = i - 1; j >= left; --j) {
array[j + 1] = array[j];
}
array[left] = key;// 填入对应位置
}
}
}
// C++代码
class BinaryInsertionSort {
public:
static void binaryInsertionSort(int array[], int length) {
for (int i = 1; i < length; ++i) {// 遍历无序序列
int left = 0;// 有序序列左指针
int right = i - 1;// 有序序列右指针
int key = array[i];// 记录准备插入的元素
while (left <= right) {
int mid = (left + right) / 2;// 有序序列中间位置
if (array[mid] < key) {// 二分查找
left = mid + 1;
} else {// array[mid] >= key两种情况合并，便于后续统一处理
right = mid - 1;
}
}
// 找到元素插入位置后，整体后移
for (int j = i - 1; j >= left; --j) {
array[j + 1] = array[j];
}
array[left] = key;// 填入对应位置
}
}
};
加载全部内容