面试必懂之数组排序法总结

1、-------寄语

    大家在理解的过程中，可以先理解排序的原理，然后按照自己的理解用代码的方式去实现；在写代码的过程中，必要时可以自己去据一个简单一点的数组，在脑海中想想排序的过程，也可以一步一步打印，看结果。这篇文章是我在网上找的，有原理图，但是原文中原理图有些错误，容易造成误导，所以我在下面的图中做了更改。

这是原文：http://www.cnblogs.com/taotingkai/p/6214367.html，大家也可以直接看我这篇文章，做了部分修改，更加好理解

2、-------分析+代码

   我们学习它是学一种思想，以后的业务逻辑中可能会用到，可能会有相似的逻辑或者培养了我们这种思想，我们今后可以举一反三。不要为了题目而题目，说了一些题外话，不好意思，言归正传。

   （1）选择排序（从小到大）

         1）思想：选择排序，让数组中的每一个数，依次与后面的数进行比较，如果前面的数大于后面的数，就进行位置的交换。这种说法或许有些人看不明白。换个说法，选择排序：第一个数依次与后面的数比较，第一次比较完之后最小的数在最前面 (即选择出最小的)。

          不理解的看看图应该就差不多了，真不明白就和明白的人讨论讨论吧。

  （2）冒泡排序（从小到大）    

         1）思想：相邻两个数进行比较，第一波比较后，最大的数在最后。（每比较完之后，后面的数就减少一个比较 ）

注意：这里是的最后一句话，应该改为"一直比较，最后一个是9，然后再从3开始第二轮冒泡，重复上面的步骤，但经过第一轮冒泡，最大的一个数已经被排到最后面了，所以没必要再比较最后一个数，但是比较了也无所谓"。

（3）插入排序

  插入排序在面试中考得比较少，这里不做详细解释，参照代码流程，自己画画流程图就懂了。      

代码：

public class ArrayTest {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] arr1= {12,10,33,40,8,22,1,4,17,66,43,28};
		selectSort1(arr1);//选择排序/也有人说这是冒泡
		System.out.println("============================");
		selectSort(arr1);//选择
		System.out.println("=========================");
		maoPao(arr1);//冒泡
		System.out.println("============================");
		insertSort(arr1);//插入
	}
	
	/**
	 * 选择排序
	 */
	public static void selectSort(int[] arr) {
		int num=0;
		for(int i=1;i<arr.length;i++) {
			int minIndex=i;
			for(int j=i;j<arr.length-1;j++) {
				num++;
				if(arr[minIndex]>arr[j]) {
					minIndex = j;
				}
			}
			if(minIndex != i) {
				int temp=arr[i];
				arr[i]=arr[minIndex];
				arr[minIndex]=temp;
			}
		}
		for (int a : arr) {
			System.out.print(a+" ");
		}
		System.out.println();
		System.out.println(num);
	}
	
	
	/**
	 * 选择排序
	 * @param arr
	 */
	public static void selectSort1(int[] arr) {
		int num=0;
		for(int i=0;i<arr.length-1;i++) {
			for(int j=i;j<arr.length-1;j++) {
				int temp;
				num++;
				if(arr[i]>arr[j+1]) {
					temp=arr[i];
					arr[i]=arr[j+1];
					arr[j+1]=temp;
				}
			}
		}
		for (int a : arr) {
			System.out.print(a+" ");
		}
		System.out.println();
		System.out.println(num);
	}
	
	/**
	 * 冒泡排序{12，10，20，9}-{10，12，9，20}-{10，9，12，20}
	 * @param arr
	 */
	public static void maoPao(int[]arr) {
		int num=0;
		for(int i=1;i<arr.length;i++) {
			for(int j=0;j<arr.length-i;j++) {
				int temp;
				num++;
				if(arr[j]>arr[j+1]) {
					temp=arr[j+1];
					arr[j+1]=arr[j];
					arr[j]=temp;	
				}
			}
		}
		for (int a : arr) {
			System.out.print(a+" ");
		}
		System.out.println();
		System.out.println(num);
	}
	
	/**
	 * 插入排序法
	 */
	public static void insertSort (int[] arr) {
		int num=0;
		for(int i=1;i<arr.length;i++) {
			for(int j=i;j>0;j--) {
				num++;
				if(arr[j-1]>arr[j]) {
					int temp=arr[j];
					arr[j]=arr[j-1];
	

控制台输出：（原数组{12,10,33,40,8,22,1,4,17,66,43,28}）

1 4 8 10 12 17 22 28 33 40 43 66 
66
============================
1 4 8 10 12 17 22 28 33 40 43 66 
55
=========================
1 4 8 10 12 17 22 28 33 40 43 66 
66
============================
1 4 8 10 12 17 22 28 33 40 43 66 
66

红色字体是我想看看一共进行了多少轮比较。

疑问：在这里我提出我小小的疑问，在我的方法中有个selectSort1（int []）；大家帮我看看这是属于冒泡还是选择，在这里我把它归为选择一类，但也有人说这是冒泡，大家帮我看看，发表一下看法，相互进步