数据结构中的排序--插入排序（升序和降序）

插入排序的基本思路就是将待排序的数字，插入到已经排好序的数列中。如果数据都在一个数组中，那么这里面会涉及到比较的次数和数据的移动，这些都会影响到算法的效率，如果是链表，就需要考虑的是指针的指向。

下面的实例代码是对一个固定的数组进行排序（升序和降序）

完整的代码：

#include "stdafx.h"
#include <iostream>
using namespace std;

void insert_ascending_sort(int data[], int n)
{
	int i = 0, j = 0, temp = 0;

	for (i = 1; i < n; i++)//开始的时候数组中的第0个元素是排好序的，直接从第二个元素开始取数据
	{
		temp = data[i];//每次都先备份好需要排序的数据
		for (j = i - 1; j >= 0 && temp < data[j]; j--)//这是升序排列，所以temp < data[j]\
如果需要降序排列temp > data[j]，如下：insert_descending_sort
		{
			data[j + 1] = data[j];//如果temp < data[j]就将j中的元素向后移动一个位置
		}
		data[j + 1] = temp;
	}
}


void insert_descending_sort(int data[], int n)
{
	int i = 0, j = 0, temp = 0;

	for (i = 1; i < n; i++)
	{
		temp = data[i];
		for (j = i - 1; j >= 0 && temp > data[j]; j--)
		{
			data[j + 1] = data[j];
		}
		data[j + 1] = temp;
	}
}

void print(int data[], int n)
{
	for (int i = 0; i < n; i++)
	{
		cout << data[i] << " ";
	}
	cout << endl;
}
int main()
{
	int num[] = {5,3, 7,4,3,9,6,2,10,4,3,7,1};
	int len = sizeof(num) / sizeof(int);

	cout << "data count:"<< len << ".  before sort: ";
	print(num, len);

	insert_ascending_sort(num, len);
	cout << "after sort: ";
	print(num, len);

	insert_descending_sort(num, len);
	cout << "after desending sort: ";
	print(num, len);

	return 0;
}

代码的测试结果：