Sort研究

  //1.BubbleSort 

package com.zhe.sort;

/**
 * sortedIndex :已排序了的数组索引，最开始都未排序，所以索引为 -1
 * @author Administrator
 *
 */
public class BubbleSort {
	public static long[] sort(long[] arr){
		long temp = 0;
		for(int sortedIndex = -1; sortedIndex <arr.length-1;sortedIndex ++){
			
			for(int cursor = arr.length-1;cursor >sortedIndex ; cursor --){
				if(cursor > 0 && arr[cursor]<arr[cursor-1]){ //防止cursor为0时，cursor-1越界
					temp = arr[cursor];
					arr[cursor] = arr[cursor-1];
					arr[cursor-1] = temp;
					
				}
			}
		}
		
		
		
		return arr;
	}
}


package com.zhe.sort;

public class InsertSort {

	/**
	 * 插入排序就是保证前面的i个有序，插入到前面有序队列的适当位置
	 * 在有序队列中比 插入数大的  都后移
	 * @param args
	 */
	
	public static long[] sort(long[] arr ){
		//i从1开始，表示第一个位置需要被插入，第0个位置之前没有与之比较的对象，所以从1开始
		for(int sortingIndex=1; sortingIndex<arr.length ; sortingIndex++){
			long temp = arr[sortingIndex];
			int cursor = sortingIndex-1;              //j记录需插入的数
			int emptyPos = sortingIndex;
			
			while(cursor>0 && arr[cursor]>temp){
				arr[emptyPos]=arr[cursor];
				emptyPos = cursor;
				cursor--;
			}
			arr[emptyPos] = temp;
		}
		return arr;
	}

		/**
		 * {3,8,9,7,6,5}
		 *        8 9
		 */
}

package com.zhe.sort;

/**
 * 这个思想是： 递归
 * 先找到一个值，然后使得左边小于这个值，右边大于这个值(数组的最后一个值为分割值)
 * --->归的部分，因为归的部分太复杂，所以搞了一个方法包装起来
 * 
 * 然后再让这两部分分别排序---->递的部分
 * 因为如果只有一个元素，那么这个元素肯定是有序的。。。
 * @author Administrator
 *
 */
public class QuickSort {
	static long[] arr;
	
	public static void sort(long[] arr,int left,int right){
		if(left > right){
			QuickSort.arr = arr;
			return ;
		}
		else{
			int middle = participate(arr,left,right);
			sort(arr, left, middle-1);
			sort(arr,middle+1,right);
		}
		
	}

	private static int participate(long[] arr,int left,int right) {
		
		int rowLeft = left; 
		int rowRight = right;
		long middleData = arr[right];
		long temp=0;
		left --;
		while(left<right){
			while(left<right&&arr[++left]<middleData);//保证left拿到的一定大于middleData
			while(left<right&&arr[--right]>middleData);//保证right拿到的一定小于middleData
		/*	while(left < right){
				if(arr[left]<middleData)left++;
				else break;
			}
			while(left<right){
				if(arr[right]>middleData)right--;
				else break;
			}*/
			if(left<right){
				temp = arr[right];
				arr[right]=arr[left];
				arr[left] = temp;
			}
		}
		arr[rowRight] = arr[right];
		arr[right] = middleData;
		return right;
	}

	public static long[] getArr() {
		return arr;
	}
}
/**
 * 1     2    3    4    7     8     9     6
 *                     left   
 * */


package com.zhe.sort;

/**
 * 与冒泡唯一的不同就是冒泡排序是 比一次交换一次，而这个是比一趟交换一次
 * sortedIndex :已排序了的数组索引，最开始都未排序，所以索引为 -1
 * @author Administrator
 *
 */
public class SelectionSort {
	
 public static long[] sort(long[] arr){
	 
	 long temp = 0;
	 for(int sortedIndex=-1; sortedIndex < arr.length-1; sortedIndex++){
		int min = arr.length-1; //假设最后一个元素是最小值
		 for(int cursor=arr.length-1; cursor>sortedIndex; cursor--){
			 if(arr[min] > arr[cursor])min=cursor;
		 }
		 temp = arr[sortedIndex+1];
		 arr[sortedIndex+1]= arr[min];
		 arr[min] = temp;
	 }
	 return arr;
 }
}

package com.zhe.sort;
/**
 * 希尔排序是插入排序的改进，他可以先跳步插入，最后再来一次插入排序
 * 最大增加幅度规则 w = w*3+1 < arr.length;的最大h 值
 * @author Administrator
 *
 */
public class ShellSort {
	public static long[] sort(long[] arr){
		//选出最优增幅
		int w = 1;
		while(w*3+1< arr.length){
			w = w*3 +1;
		}
		while(w>0){
			//插入排序，因为第0个对象已经排序完毕，所以第一个对象是0+h=h
			//因为是分成h组，所以每一组的第一个都被认为是有序的
			for(int sortingIndex = w ;sortingIndex < arr.length ;sortingIndex++){
				long temp = arr[sortingIndex];
				int emptyPos = sortingIndex;
				int cursor = emptyPos -w;
				while(cursor >=0){
					if(arr[cursor]> temp){
						arr[emptyPos] = arr[cursor];
						emptyPos = cursor;
					}
					cursor -= w;
				}
				arr[emptyPos] = temp;
			}
			w = (w-1)/3; 		
		}
		return arr;
	}
}


当n较小时，对稳定性不做要求时用选择排序(他不是挨着操作元素)，对稳定性有要求时用插入或者冒泡
当n较大时，关键元素比较随机，对稳定性没要求用快速排序，但是元素基本有序的话快速就变成了冒泡排序，因为不管怎么样他都会递归的
当n较大时，元素可能出现本身有序，对稳定性没要求用堆排序。(建立堆的过程比较漫长)
当n较大时，元素可能出现本身有序，对稳定性有要求，空间允许情况下用归并排序