常用排序算法

      排序在程序开发的过程中还是比较常用的，例如二分查找法比线性查找法要快的多，然而二分法只能应用于有序的数据，简单的说排序有时候会作为查找的一个初始步骤；也很有可能按照某项业务需求对数据进行排序。目前比较常用的排序算法也就是：冒泡、选择和插入排序，还有高级点的希尔排序和快速排序。

 

• 冒泡排序：

 

 冒泡排序是许多人学习的前几种排序算法之一。它很大的优点是简单，如果在某种情况下需要一种可以快速编程的小排序算法，就可以选择冒泡排序。冒泡算法的思路比较容易理解，就是连续的扫描待排序的记录,每扫描一次，都会移动最大的记录，使之更接近于顶部，就像气泡一样缓慢上升。

 

int out,in;
for(out = testArray.length -1; out> 1; out--)
     for(in=0; in<out; in++)
	if(testArray[in] > testArray[in+1])
		swap(in,in+1);
------------------------------------------------------------------------------------------
private static void swap(int one ,int two){
		int temp = testArray[one];
		testArray[one] = testArray[two];
		testArray[two] = temp;
}

 

 要将最小的数据项放在数组的最开始(数组下标为0)，并将最大的数据项放在数组的最后(数组下标n-1)。外层for循环的计算器out从数组的最后开始，下标大于out的数据项表示都已经是排好序的。变量out在每完成一次循环后左移一位，因此算法就不再处理那些已排好序的数据项了。

 

 

• 选择排序：

 

选择排序就是把所有的元素扫描一次，从中选择出最小的元素将有序的队员都排在队列的左边，而冒泡排序中则是排列在队列的最右边。

 

int out,in,min;
for(out=0; out<testArray.length-1; out++)
{
	min = out;
	for(in = out+1; in<testArray.length; in++){
		if(testArray[in]<testArray[min])
			min = in;
		swap(out,min);
	}
}

 从数组开头开始(数组下标为0)向高位增长，内层循环变量in，从out所指变量的下一位开始，同样是向右位移。依次比较如果内层循环得到的项目数据更小则交换。

 

 

 

• 插入排序

 

从数组的第二个元素开始，向右移动。使用外层变量out标识未排序部分最左端的数据。在内层的while循环中,in变量从out开始，向左移动，依次比较数组元素。

int in,out;
for(out =1; out< testArray.length; out++){
	int temp = testArray[out];
	in = out;
	while(in > 0 && testArray[in-1] >= temp){
		testArray[in] = testArray[in-1];
		--in;
	}
	testArray[in] = temp;
}