Java教程

插入排序算法

本文主要是介绍插入排序算法,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

插入排序的核心思想是:
1 向一个已有序的队列中插入数据,
n个数,那么只需要插入n-1次

实现如下:
将第一个数看作一个自然有序的队列.

#include <iostream>
#include <algorithm>
using namespace std;
void InsertSoft(int* a,int length)
{
    if(a != NULL && length > 0)
    {
        for(int i = 1;i < length;i++)
        {
            int curValue = a[i];
            int prevIndex = i - 1;
            while(curValue < a[prevIndex] && prevIndex > 0)
            {
                a[prevIndex + 1] = a[prevIndex];
                prevIndex--;
            }
            a[prevIndex + 1] = curValue;
        }
    }
}
int main()
{
	int a[] ={0,1,2,65,54,20,30,40,20};
	int lengthA = sizeof(a) / sizeof(a[0]);
    InsertSoft(a,lengthA);
 	std::for_each(a,a+lengthA,[](int i){
 	    std::cout << i << std::endl;});
	return 0;
}

注:插入排序是稳定排序,因为在排序过程中,相同值的相对大小关系未发生改变。
外层循环控制将要插入的数据,内层循环控制,比较和移动。

这篇关于插入排序算法的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!