6.快速排序
（1）基本思想：选择一个基准元素,通常选择第一个元素或者最后一个元素,通过一趟扫描，将待排序列分成两部分,一部分比基准元素小,一部分大于等于基准元素,此时基准元素在其排好序后的正确位置,然后再用同样的方法递归地排序划分的两部分。
（2）实例：
（3）用java实现
1 public class quickSort {
2 int a[]={49,38,65,97,76,13,27,49,78,34,12,64,5,4,62,99,98,54,56,17,18,23,34,15,35,25,53,51};
3 public quickSort(){
4 quick(a);
5 for(int i=0;i<a.length;i++)
6 System.out.println(a);
7 }
8 public int getMiddle(int[] list, int low, int high) {
9 int tmp = list[low]; //数组的第一个作为中轴
10 while (low < high) {
11 while (low < high && list[high] >= tmp) {
12
13 high--;
14 }
15 list[low] = list[high]; //比中轴小的记录移到低端
16 while (low < high && list[low] <= tmp) {
17 low++;
18 }
19 list[high] = list[low]; //比中轴大的记录移到高端
20 }
21 list[low] = tmp; //中轴记录到尾
22 return low; //返回中轴的位置
23 }
24 public void _quickSort(int[] list, int low, int high) {
25 if (low < high) {
26 int middle = getMiddle(list, low, high); //将list数组进行一分为二
27 _quickSort(list, low, middle - 1); //对低字表进行递归排序
28 _quickSort(list, middle + 1, high); //对高字表进行递归排序
29 }
30 }
31 public void quick(int[] a2) {
32 if (a2.length > 0) { //查看数组是否为空
33 _quickSort(a2, 0, a2.length - 1);
34 }
35 }
36 }
7、归并排序
（1）基本排序：归并（Merge）排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。
（2）实例：
（3）用java实现
1 import java.util.Arrays;
2
3 public class mergingSort {
4 int a[]={49,38,65,97,76,13,27,49,78,34,12,64,5,4,62,99,98,54,56,17,18,23,34,15,35,25,53,51};
5 public mergingSort(){
6 sort(a,0,a.length-1);
7 for(int i=0;i<a.length;i++)
8 System.out.println(a);
9 }
10 public void sort(int[] data, int left, int right) {
11 // TODO Auto-generated method stub
12 if(left<right){
13 //找出中间索引
14 int center=(left+right)/2;
15 //对左边数组进行递归
16 sort(data,left,center);
17 //对右边数组进行递归
18 sort(data,center+1,right);
19 //合并
20 merge(data,left,center,right);
21
22 }
23 }
24 public void merge(int[] data, int left, int center, int right) {
25 // TODO Auto-generated method stub
26 int [] tmpArr=new int[data.length];
27 int mid=center+1;
28 //third记录中间数组的索引
29 int third=left;
30 int tmp=left;
31 while(left<=center&&mid<=right){
32
33 //从两个数组中取出最小的放入中间数组
34 if(data[left]<=data[mid]){
35 tmpArr[third++]=data[left++];
36 }else{
37 tmpArr[third++]=data[mid++];
38 }
39 }
40 //剩余部分依次放入中间数组
41 while(mid<=right){
42 tmpArr[third++]=data[mid++];
43 }
44 while(left<=center){
45 tmpArr[third++]=data[left++];
46 }
47 //将中间数组中的内容复制回原数组
48 while(tmp<=right){
49 data[tmp]=tmpArr[tmp++];
50 }
51 System.out.println(Arrays.toString(data));
52 }
53
54 }
组图打开中，请稍候......
收藏
淘帖
踩
