ֱ

最近对排序算法的复习

// 直接插入排序.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include "iostream.h"

/*插入排序算法的原理：
*1. 首先将数组的第一个数A[0]看成是排好序的
*2. 然后从第二个元素开始和它前面的元素进行比较，如果从前面的某一个数大，就交换。
*由于前面的元素是有序的，所以就使有序元素的个数逐渐增大，直到等于n。
*插入排序是稳定的 ，插入排序的时间复杂度为O(n2)。
*最坏的情况就是要插入的数比下标为0的数小，循环比较交换时要一直比到最前面，然后把它放在第一个元素上。
*所以，当整个待排序数组时反序时（如6,5,4,3,2,1)时，运行时间最
*/

void Swap(int &x,int &y) {
	int temp = x;
	x = y;
	y = temp;
}

void insert_px(int array[],int length) {
	for(int i=1;i<length;i++) {
		for(int j=i;j>0;j--) {
			if(array[j]<array[j-1]) {
				Swap(array[j-1],array[j]);
			}
		}
	}
}

int main(int argc, char* argv[])
{
	int array[] = {23,54,12,34,97,60,58,7,73,82};
	for(int i=0;i<10;i++) {
		cout<<array[i]<<" ";
	}
	cout<<endl;
	
	insert_px(array,10);

	for(i=0;i<10;i++) {
		cout<<array[i]<<" ";
	}
	cout<<endl;
	return 0;
}