三、排序

2013-03-01

3、排序一、选择排序(selectionSort)?基本思想：? ? 每一趟从待排序的数据元素中选出最小（或最大）的一个元素，

3、排序

一、选择排序(selectionSort)

基本思想：

? ? 每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。

二、冒泡排序(bubbleSort)

基本思想：

比较相邻的元素。如果第一个比第二个大，就交换他们两个。对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。针对所有的元素重复以上的步骤，除了最后一个。持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。冒泡和选择很相似，每一轮比较都是找出最值，不同的是找最值的方式不同

三、插入排序(insertSort)

基本思想：

? ? 始终保证前面的数是有序的，然后将后面一个数 x 取出，依次向前比较，直到大于等于前面某个数，或者到头了，那么这时的位置就是x应该放的位置，再重复操作

三、排序
?

四、快速排序(quickSort)

快速排序是C.R.A.Hoare于1962年提出的一种划分交换排序。它采用了一种分治的策略，通常称其为分治法

分治法的基本思想是：将原问题分解为若干个规模更小但结构与原问题相似的子问题。递归地解这些子问题，然后将这些子问题的解组合为原问题的解。

快速排序的基本思想：

? ? 设当前待排序的无序区为R[left..right]，利用分治法可将快速排序的基本思想描述为：

a,分解

划分的关键是要求出基准记录所在的位置pivotpos

b，求解

通过递归调用快速排序对左、右子区间R[left..pivotpos-1]和R[pivotpos+1..right]快速排序。

c，组合

因为当"求解"步骤中的两个递归调用结束时，其左、右两个子区间已有序。对快速排序而言，"组合"步骤无须做什么，可看作是空操作

以下是具体代码：

class SortDemo {public static void main(String[] args) {int[] arr = new int[]{5,3,6,8,4,6,9,2};//选择排序//selectionSort(arr);//冒泡排序//bubbleSort(arr);//插入排序//insertSort(arr);//快速排序quickSort(arr,0,arr.length-1);for(int x=0;x<arr.length-1;x++){System.out.print(arr[x]+",");}System.out.println(arr[arr.length-1]);}//选择排序public static void selectionSort(int[] arr){for(int x=0;x<arr.length-1;x++){for(int y=x+1;y<arr.length;y++){if(arr[x]>arr[y]){swap(arr,x,y);}}}}//冒泡排序public static void bubbleSort(int[] arr){for(int x=0;x<arr.length-1;x++)//只需要比较arr.length-2次{//-x是因为每次比较后最后一个都是最值，不用再比较了  -1是为了防止角标越界for(int y=0;y<arr.length-x-1;y++){if(arr[y]>arr[y+1]){swap(arr,y,y+1);}}}}//插入排序public static void insertSort(int[] arr){//从1开始，因为为0时只有一个数，无需比较for(int x=1;x<arr.length;x++){//用temp记录要插入的数，相当于留一个空位int temp = arr[x];//x-1是有序数据的最大角标，插入就在有序的数据中插入int y = x-1;for(;y>=0 && arr[y]>temp;y--){//如果y>=0，并且arr[y]大于temp就把arr[y]向后移一位arr[y+1] = arr[y];}//比较完成后y+1就是temp该放的位置arr[y+1] = temp;}}//快速排序public static void quickSort(int[] arr,int left,int right){//对arr[left,right]快速排序int pivotpos;//划分后的基准的记录位置//仅当区间长度大于1时才排序if(left < right){//对arr[left,right]做划分pivotpos = partition(arr,left,right);quickSort(arr,left,pivotpos-1);//对左区间递归排序quickSort(arr,pivotpos+1,right);//对右区间递归排序}}//取得基准位置，划分区域private static int partition(int[] arr,int left,int right){//取区间最左边的数最为基准数int pivot = arr[left];int pivotpos;//记录pivot所在的位置int x = left;int y = right;while(x < y){//先从右边开始找第一个小于pivot的数，要保证 x<y//因为比如说第一个数是最小的，那么没有x<y那么y--最后就会等于-1while(arr[y] >= pivot && x < y)y--;//x = y的时候不用交换if(x < y)swap(arr,x,y);//再从左边开始找第一个大于pivot的数，要保证 x<ywhile(arr[x] <= pivot && x < y)x++;if(x < y)swap(arr,x,y);}//一轮比较后x的值就是pivotpos也就是pivot所在的位置pivotpos = x;return pivotpos;}//交换数组中两个数的位置public static void swap(int[] arr,int x,int y){int temp = arr[x];arr[x] = arr[y];arr[y] = temp;}}

五、Arrays.sort(arr);//java中已经定义好的一种排序方式，开发中，对数组排序，要使用该句代码

热点排行

编程

三、排序