黑马程序员技术交流社区
标题: 排序算法之直接插入排序 [打印本页]
作者: 专注的一批 时间: 2019-10-21 12:10
标题: 排序算法之直接插入排序
1、介绍。
直接插入排序是一种简单的插入排序法，其基本思想是：把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列。例如,已知待排序的一组记录是：60,71,49,11,24,3,66。假设在排序过程中，前3个记录已按关键码值递增的次序重新排列，构成一个有序序列：49,60,71。将待排序记录中的第4个记录（即11）插入上述有序序列，以得到一个新的外汇返佣http://www.kaifx.cn/含4个记录的有序序列。首先，应找到11的插入位置，再进行插入。可以将11放入数组的第一个单元r[0]中，这个单元称为监视哨，然后从71起从右到左查找，11小于71，将71右移一个位置，11小于60，又将60右移一个位置，11小于49，又再将49右移一个位置，这时再将11与r[0]的值比较，11≥r[0]，它的插入位置就是r[1]。假设11大于第一个值r[1]。它的插入位置应该在r[1]和r[2]之间，由于60已经右移了，留出来的位置正好留给11.后面的记录依照同样的方法逐个插入到该有序序列中。若记录数n,续进行n-1趟排序，才能完成。
直接插入排序是稳定排序，不需要额外内存，空间复杂度O(1)。时间复杂度，最佳情况：O(n) 最差情况：O(n^2) 平均情况：O(n^2)。
2、步骤。
(1)设置监视哨r[0]，将待插入记录的值赋值给r[0]；
(2)设置开始查找的位置j；
(3)在数组中进行搜索，搜索中将第j个记录后移，直至r[0].key≥r[j].key为止；
(4)将r[0]插入r[j+1]的位置上。
3、代码。
public static void main(String[] args) {
System.out.println("------开始------");
//生成生成两份随机数组，其中用系统自带的方法进行排序，到时候进行验证。
final int number = 100000;
int[] sortArray = new int[number];
int[] sortArrayCopy = new int[number];
for (int i = 0; i < sortArray.length; i++) {
sortArray = (int) (Math.random() * number);
}
System.arraycopy(sortArray, 0, sortArrayCopy, 0, number);//数组复制
Arrays.sort(sortArrayCopy);
//开始排序
long startTime = System.currentTimeMillis();
directInsertSort(sortArray);//直接插入排序
System.out.println("花费时间：" + (System.currentTimeMillis() - startTime));
//跟系统排序之后数组进行比较，查看是否排序成功。
if (Arrays.equals(sortArray, sortArrayCopy)) {
System.out.println("排序成功");
} else {
System.out.println("排序失败");
}
System.out.println("------结束------");
}
//直接插入排序 最佳情况：T(n) = O(n) 最坏情况：T(n) = O(n2) 平均情况：T(n) = O(n2)
private static void directInsertSort(int[] array) {
for (int i = 1; i < array.length; i++) {//n-1轮 第一个无需排序
int curIndex = i;
while (curIndex > 0) {
if (array[curIndex] > array[curIndex - 1]) {
break;
}
int flag = array[curIndex];
array[curIndex] = array[curIndex - 1];
array[curIndex - 1] = flag;
curIndex--;
}
}
}
#include <stdio.h>
void InsertSort(int k[], int n)
{
int i, j, temp;
//i=1,因为需要j指向前一个元素
for(i = 1; i < n; i++)
{
//进行重新排序，后面的元素小于前面的元素
if (k < k[i-1])
{
temp = k;
//一个一个地往后推，推到相应位置，然后把temp插进去
for (j = i -1; k[j] > temp; j--)
{
k[j+1] = k[j];//找位置，同时向后推移
}
k[j+1] = temp;
}
}
}
int main(void)
{
int i, a[10] = {5, 2, 6, 0, 3, 9, 1, 7, 4, 8};
InsertSort(a, 10);
printf("排序后的结果是：");
for (i = 0; i < 10; i++)
{
printf("%d", a);
}
printf("\n\n");
return 0;
}
#include <iostream>
using namespace std;
void insertSort(int a[],int n){
int tmp,j;
for(int i=1;i<n;i++){//遍历无序部分
tmp=a;
j=i-1;
//将无序最左侧的元素和有序部分进行比较
while(j>=0&&tmp<a[j]){
//将有序部分元素大于a的向后移
a[j+1]=a[j];
j--;
}
a[j+1]=tmp;//把带插入元素放到合适的位置
}
}
int main()
{
int a[]={9,8,7,6,5,4,3,2,1,0};
insertSort(a,10);
for(int i=0;i<10;i++){
cout << a << endl;
}
return 0;
}
#include <stdio.h>
void InsertSort(int arr[],int len)
{
int i = 1;
int temp;
int j;
for(i;i < len;i++)
{
temp = arr;
for(j = i-1;j >= 0 && arr[j] > temp;j--)
{
arr[j + 1] = arr[j];
}
arr[j+1] = temp;
}
}
void Show(int arr[],int len)
{
for(int i = 0;i < len;i++)
{
printf("%d ",arr);
}
}
int main()
{
int arr[] = {87,8,59,24,9};
int len = sizeof(arr)/sizeof(arr[0]);
InsertSort(arr,len);
Show(arr,len);
}
算法分析
时间复杂度：
正序（关键字递增有序）：不进入内循环。外循环进行 n-1趟，也即是比较了n-1次（tmp<a[j]）；每趟进行2次赋值（tmp=a;a[j+1]=tmp;）
正序的关键字比较次数最小和元素移动最小次数
反序（关键字递减）：关键字比较R[0……都学要比较就是i次；内循环移动R[0……都要后移，再加上外面（tmp=a;a[j+1]=tmp;）共有i+2。
正序的关键字比较次数最大和元素移动最大次数
对于R(1<=i<=n-1)插入到有序区R[0……中，平均比较次数i/2;平均移动数i/2+2。所以平均时间复杂度：
空间复杂度：
只是用了i,j,tmp，与问题规模无关，空间复杂度为O(1)
| 欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/) |
黑马程序员IT技术论坛 X3.2 |