排序的算法

• • 一、冒泡排序
  • 二、选择排序
  • 三、快速排序
  • 四、插入排序

小结：

   思路：重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

	public static int[] bubbleSort(int[] array){
		if(array.length > 0){
			for(int i = 0;i array[j+1]){
						int temp = array[j];
						array[j] = array[j+1];
						array[j+1] = temp;
					}
				}
			}
		}
		return array;
	}

最佳情况：T(n) = O(n) 最差情况：T(n) = O(n2) 平均情况：T(n) = O(n2)

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

	public static int[] selectionSort(int[] array){
		if(array.length > 0){
			for(int i = 0;i 
最佳情况：T(n) = O(n2) 最差情况：T(n) = O(n2) 平均情况：T(n) = O(n2)
 
三、快速排序 
 
   思路：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。
 
	public static void QuickSort(int[] array,int low,int hight){
		//if (array.length < 1 || low < 0 || hight >= array.length || low > hight) return null;
		if(low < hight){
			int privotpos = partition(array,low,hight);
			QuickSort(array,low,privotpos - 1);
			QuickSort(array,privotpos + 1,hight);			
		}
	
	}
	public static int partition(int[] array,int low,int hight){
		int privot = array[low];
		while(low < hight){
			while(low < hight && array[hight] >= privot) --hight;
			array[low] = array[hight];
			while(low < hight && array[low] <= privot) ++low;
			array[hight] = array[low];
		}
		array[low] = privot;
		return low;			
	}
 
四、插入排序 
 
   思路：通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。
 
	public static int[] insertSort(int[] array){
		if(array.length > 0){			
			for(int i = 0 ;i= 0 && current < array[index]){
					array[index + 1] = array[index]; 
					index--;
				}
				array[index+1] = current;
			}
		}
		return array;
	}
 
五、希尔排序
 
六、归并排序
 
七、基数排序
 八、计数排序
 九、桶排序
 十、堆排序