基本排序算法分析

     在学习数据结构的时候，针对数组，有几种典型的排序算法，分别为冒泡排序、插入排序、选择排序和希尔排序，这几种排序算法也是比较常见的。下面是对这些排序算法的一些理解。

     要很好的理解排序算法，我觉得最重要是掌握程序执行的流程，并且一个个地试数。试过几次数后，用到的排序算法也就难理解了。

     冒泡排序

     冒泡排序算法应该说是排序算法中最简单的。但能一次性的写对冒泡排序也是不容易的。冒泡排序最核心的策略就是每次找出最大值(或者最小值)并把其放入到数组的最末端(或者最前端)，要排序的元素每次减少1个，以此不断执行，最后就会得到想要的结果。下面是其具体的代码实现：

    

	/**
	 * 冒泡排序策略：搜索整个数组，比较相邻元素，如果两者的相对大小次序不对，则交换它们，其结果是最大值
	 * “像水泡一样”移动到数组的最后一个位置上，这也是它在完成排序的数组中合适的位置；然后再次搜索数组，
	 * 将第二大的值移动到倒数第二个位置上，重复该过程，直至将所有元素移动到正确的位置上
	 */
	static void sortBubb(int [] arr){
		//数组中有length个数，只需要排length-1次
		for(int i=0;i<arr.length-1;i++){
			//每经过一次排序，就将本次排序中最大的元素放到排序数组的最后一位
			//每经过一次排序，要排序的数组元素的个数就减1
			for(int j=0;j<arr.length-i-1;j++){
				//比较相邻元素的大小，如果后一个元素小于前一个元素，就交换这两个元素，否则什么事也不做
				if(arr[j] > arr[j+1]){
					int temp = arr[j];
					arr[j] = arr[j+1];
					arr[j+1] = temp;
				}
			}
		}
	}

    插入排序

    插入排序的核心思想就是将要插入的元素和已排好序的元素进行比较，并将新元素插入到数组的适当位置。可以分为两步：先比较，再插入。下面是代码实现。

    

	/**
	 * 插入排序策略：首先按大小秩序排序数组中的前两个值，然后在相对于前两个值的适当位置插入数组的第三个值
	 * 再在相对于数组前三个值得适当位置插入数组的第四个值，以此类推。每进行以此插入操作，有序子集中的数值个
	 * 数将递增1.重复此过程，直到数组中的所有值都按照秩序排列为止
	 */
	static void sortInsert(int arr[]){
		//先将arr[0]和arr[1]比较，每次比较的元素个数加1
		for(int i=1;i<arr.length;i++){
			for(int j=i;j>0;j--){
				if(arr[j] < arr[j-1]){
					int temp = arr[j];
					arr[j] = arr[j-1];
					arr[j-1] = temp;
				}
			}
		}
	}

    选择排序

    选择排序的核心思想就是先找值，再替换。也就是说,先在数组中找出最大值(或者最小值)，然后再将它与数组的最大下标(或最小下标)处的值替换。具体代码如下：

    

	/**
	 * 选择排序策略：搜索整个数组，找到最小值。将该值与数组中的第一个位置上的值进行交换
	 * 搜索剩下的数组元素(第一个除外)，找到其中的最小值，然后将其与数组中第二个位置上的
	 * 值进行交换。对数组中的每个位置重复该过程。在该算法结束时，就完成了对数组的排序。
	 */
	static void sortSelect(int[] arr){
	 for(int i=0;i<arr.length;i++){
		 int lowerIndex = i;
		 for(int j=i+1;j<arr.length;j++){
			 if(arr[j]<arr[lowerIndex]){
				 lowerIndex = j;
			 }
		 }
		 int temp = arr[i];
		 arr[i] = arr[lowerIndex];
		 arr[lowerIndex] = temp;
	 }
	}

   希尔排序

   希尔排序的效率是比较高的，它的核心思想就是将数组不断分为更小的几个序列，在序列内先进行排序，排好之后再进行一次插入排序。它的实现具体如下：

   

	/**
	 * 希尔排序策略：希尔排序又称为”缩小增量排序“，先将整个待排序的元素序列分割成若干个子序列（由相隔某
	 * 个”增量“的元素组成）分别进行直接插入排序，然后依次缩减增量再进行排序，待整个序列中的元素基本有序（
	 * 增量足够小）时，再对全部元素进行依次直接插入排序
	 */
	static void sortShell(int[] arr){
		//不断缩小增量
		for(int increment = arr.length/2;increment>0;increment/=2){
			//从一半的位置开始比较
			for(int i=increment;i<arr.length;i++){
				int temp = arr[i];
				int j = 0;
				for(j=i;j>=increment;j-=increment){
					if(temp < arr[j-increment]){
						arr[j] = arr[j-increment];
					}else{
						break; 
					}
				}
				arr[j] = temp;
			}
		}
	}

评论

1 楼 LADigni 2012-04-02