黑马程序员-排序方法小结

---------------------- ASP.Net+Android+IO开发S、.Net培训、期待与您交流！ ----------------------

    作为一个初学者，排序算法可能是接触到的最早的逻辑实例了，而且这些个逻辑还确实有点伤脑筋，那我就将一些经典的排序算法记下来吧，以后也可以来瞧瞧。

    一、冒泡排序

     最直接、最好理解、初学者最容易想到的排序算法！但是好像效率在大量的数据方面有些不足。    

     冒泡排序算法的运作如下(升序)：

1. 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
2. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
3. 针对所有的元素重复以上的步骤，除了最后一个。
4. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

    用java代码实现：       

        public void bubbleSort(int[] arr) {
		int m = 0;
		for (int i = 0; i < arr.length - 1; i++) {
			for (int j = 0; j < arr.length - i - 1; j++) {
				if (arr[j] > arr[j+1]) {
					m = arr[j];
					arr[j] = arr[j+1];
					arr[j+1] = m;
				}
			}
		}
	}

  二、选择排序

      首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

     这种方法因为每一次只需要交换一次特定的数据，所以可以将需要交换的数据记录到内存里边，等一轮判断完毕之后，再交换存放在堆中的数据，这样可以提高效率。。

  用java代码实现

 

	public static void selectSort(int[] arr){
		for(int i=0; i<arr.length; i++){
			int temp = i;
			for(int j=i+1; j<arr.length; j++){				
				if(arr[temp] > arr[j]){
					temp = j;
				}
			}
			int x = arr[i];
			arr[i] = arr[temp];
			arr[temp] = x;
		}
	}

    三、插入排序

      工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。就是将数组第一个值看做有序的，从后每一个值放进来的时候，找放的位置。这里边就需要一些已经排好的数据可能会整体左移或者右移，所以用插入排序的算法也可以找到新数据存放到有序数组中的位置

      用java代码实现：

     

	public static void insertSort(int[] arr) {
		//定义循环控制变量
		int i, j;
		//定义哨兵
		int guard;
		for (i = 1; i < arr.length; i++) {
			if (arr[i] < arr[i - 1]) {
				guard = arr[i];
				j = i - 1;
				do {
					arr[j + 1] = arr[j];
					j--;
				} while (j != -1 && guard < arr[j]);
				arr[j + 1] = guard;
			}
		}
	}

 

以上是三种最基本的排序算法，现在效率最高的并不在里面，而是一种叫做希尔排序的算法，有时间我还得去研究下，目前最主要的是先好好学基本的东西，深入了解可以放到后面。

 

---------------------- ASP.Net+Android+IOS开发、.Net培训、期待与您交流！ ----------------------

详细请查看：http://edu.csdn.net