求大神帮忙解释下数组中的这三种数组排序冒泡排序，交换排序和快速排序。一直数组都是我的软肋，有木有，举手啊。

陈云展 发表于 2012-11-4 21:33

自己总结的

这里给你推荐一个好网站

建议：静下心。debug。思考。总结。

不错，我试试

葬天 发表于 2012-11-4 20:44
/**
排序练习
@author yangmeicheng

嗯，好的

1. package com.itheima;
   
2. 
   
3. import java.util.Arrays;
   
4. 
   
5. /**
   
6. * 1、 排序有哪几种方法？请列举。并用JAVA实现一个快速排序.
   
7. *
   
8. * @author snow
   
9. *
   
10. */
    
11. public class Test1 {
    
12.         public static void main(String[] args) {
    
13.                 int arr[] = new int[] { 10, 8, 20, 11, 19 };
    
14.                 // int[] a = {2, 34, 2};// 一个数组的定义和实例化
    
15.                 // System.out.println(Arrays.toString(sort2(arr)));
    
16.                 System.out.println(Arrays.toString(sort4(arr, 0, arr.length - 1)));
    
17.                 System.out.println(Arrays.toString(sort6(arr, arr)));
    
18.         }
    
19. 
    
20.         // 冒泡排序法
    
21.         public static int[] sort1(int[] arr) {
    
22.                 for (int i = 0; i < arr.length; i++) {
    
23.                         int temp = 0;
    
24.                         for (int j = 0; j < arr.length - i - 1; j++) {
    
25.                                 if (arr[j] > arr[j + 1]) {
    
26.                                         temp = arr[j];
    
27.                                         arr[j] = arr[j + 1];
    
28.                                         arr[j + 1] = temp;
    
29.                                 }
    
30.                         }
    
31.                 }
    
32.                 return arr;
    
33.         }
    
34. 
    
35.         // 插入排序法
    
36.         public static int[] sort2(int[] arr, int left, int right) {
    
37.                 for (int i = left, j = i; i < right; j = ++i) {
    
38.                         int arri = arr[i + 1];
    
39.                         while (arri < arr[j]) {
    
40.                                 arr[j + 1] = arr[j];
    
41.                                 if (j-- == left) {
    
42.                                         break;
    
43.                                 }
    
44.                         }
    
45.                         arr[j + 1] = arri;
    
46.                 }
    
47.                 return arr;
    
48.         }
    
49. 
    
50.         // 选择排序法
    
51.         public static int[] sort3(int[] arr) {
    
52.                 for (int i = 0; i < arr.length - 1; i++) {
    
53.                         int j = i;
    
54.                         int temp = 0;
    
55.                         for (int k = i + 1; k < arr.length; k++) {
    
56.                                 if (arr[k] < arr[j]) {
    
57.                                         j = k;
    
58.                                 }
    
59.                         }
    
60.                         if (j != i) {
    
61.                                 temp = arr[j];
    
62.                                 arr[j] = arr[i];
    
63.                                 arr[i] = temp;
    
64.                         }
    
65.                 }
    
66.                 return arr;
    
67.         }
    
68. 
    
69.         // 快速排序法
    
70.         /**
    
71.          * 快速排序思想： 1，首先找到中间的数，i初始为0递增，直到大于或等于中间的数。j初始为length-1递减，直到小于或者等于中间的数。
    
72.          * 2，交换i，j所指向的数。
    
73.          * 3，递归调用该方法。
    
74.          * @param arr
    
75.          * @param left
    
76.          * @param right
    
77.          * @return
    
78.          */
    
79.         public static int[] sort4(int[] arr, int left, int right) {
    
80.                 int i = left, j = right;
    
81.                 int middle, temp;
    
82. 
    
83.                 middle = arr[(left + right) / 2];
    
84.                 do {
    
85.                         while ((arr[i] < middle) && (i < right)) {
    
86.                                 i++;
    
87.                         }
    
88.                         while ((arr[j] > middle) && (j > left)) {
    
89.                                 j--;
    
90.                         }
    
91.                         if (i <= j) {
    
92.                                 temp = arr[i];
    
93.                                 arr[i] = arr[j];
    
94.                                 arr[j] = temp;
    
95.                                 i++;
    
96.                                 j--;
    
97.                         }
    
98.                 } while (i <= j);
    
99.                 if (left < j) {
    
100.                         sort4(arr, left, j);
     
101.                 }
     
102. 
     
103.                 if (right > i)
     
104.                         sort4(arr, i, right);
     
105.                 return arr;
     
106.         }
     
107. 
     
108.         public static int[] sort5(int[] arr, int step) {
     
109.                 int min;
     
110.                 int temp;
     
111. 
     
112.                 int sequence = 1;
     
113.                 while (sequence < arr.length / step) {
     
114.                         sequence = sequence * step + 1; // 产生到以step为步长到arr.length的最大值.
     
115.                 }
     
116. 
     
117.                 while (sequence > 0) {
     
118. 
     
119.                         for (int i = sequence; i < arr.length; i++) {
     
120.                                 temp = arr[i];
     
121.                                 min = i;
     
122. 
     
123.                                 while (min > sequence - 1 && arr[min - sequence] > temp) {
     
124.                                         arr[min] = arr[min - sequence];
     
125.                                         min = min - sequence;
     
126.                                 }
     
127. 
     
128.                                 arr[min] = temp;
     
129.                         }
     
130. 
     
131.                         sequence = (sequence - 1) / step; // 递减序列关键字
     
132.                 }
     
133.                 return arr;
     
134.         }
     
135. 
     
136.        
     
137.         /**
     
138.          * 归并操作的工作原理如下：
     
139.          * 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
     
140.          * 设定两个指针，最初位置分别为两个已经排序序列的起始位置
     
141.          * 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
     
142.          * 　重复步骤3直到某一指针达到序列尾
     
143.          * 将另一序列剩下的所有元素直接复制到合并序列尾
     
144.          * @param data1
     
145.          * @param data2
     
146.          * @return
     
147.          */
     
148.         public static int[] sort6(int[] data1, int[] data2) {
     
149.                 int[] temp = new int[data1.length + data2.length];
     
150.                 int i = 0, j = 0, iter = 0;
     
151.                 for (; i < data1.length && j < data2.length;) {
     
152.                         if (data1[i] <= data2[j]) {
     
153.                                 temp[iter] = data1[i];
     
154.                                 iter++;
     
155.                                 i++;
     
156.                         } else {
     
157.                                 temp[iter] = data2[j];
     
158.                                 iter++;
     
159.                                 j++;
     
160.                         }
     
161.                 }
     
162.                 for (; i < data1.length; i++, iter++) {
     
163.                         temp[iter] = data1[i];
     
164.                 }
     
165.                 for (; j < data2.length; j++, iter++) {
     
166.                         temp[iter] = data2[j];
     
167.                 }
     
168.                 return temp;
     
169.         }
     
170. 
     
171. }
     

复制代码

• 自己总结的
• 这里给你推荐一个好网站
• 建议：静下心。debug。思考。总结。
• http://en.wikipedia.org/wiki/Sorting_algorithm
  

/**
排序练习
@author yangmeicheng
*/
class SortTest
{
        public static void main(String[] args)
        {
                int [] arr = new int[] {1,78,34,13,14,20};
                System.out.println("排序前：");
                printArray(arr);
                //sortSelect(arr);
                //bubbleSort(arr);
                //insertSort(arr);
                quickSort(arr,0,arr.length-1);
                System.out.println("排序后");
                printArray(arr);
        }

        /**
        选择排序算法
        原理：工作原理如下。首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，
                  然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
              以此类推，直到所有元素均排序完毕。
        复杂度分析：选择排序的交换操作介于和次之间。选择排序的比较操作为次之间。选择排序的赋值操作介于和次之间。
                    比较次数O(n^2),比较次数与关键字的初始状态无关，总的比较次数N=(n-1)+(n-2)+...+1=n*(n-1)/2。
                                交换次数O(n),最好情况是，已经有序，交换0次；最坏情况是，逆序，交换n-1次。
                                交换次数比冒泡排序少多了，由于交换所需CPU时间比比较所需的CPU时间多，n值较小时，选择排序比冒泡排序快。
        @param arr待排序数组
        */
        public static void sortSelect( int [] arr )
        {
                for (int i=0; i<arr.length-1; i++ )
                {
                        for(int j=i+1; j<arr.length; j++)
                        {
                                if(arr[j] < arr[i])
                                {
                                        arr[j] = arr[i]^arr[j];
                                        arr[i] = arr[i]^arr[j];
                                        arr[j] = arr[i]^arr[j];
                                }
                        }
                }
        }

        /**
        完成冒泡排序
        原理：
                比较相邻的元素。如果第一个比第二个大，就交换他们两个。
                对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
                针对所有的元素重复以上的步骤，除了最后一个。
                持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
                由于它的简洁，冒泡排序通常被用来对于程式设计入门的学生介绍算法的概念。
        复杂度分析：冒泡排序对个项目需要O()的比较次数，且可以原地排序。尽管这个算法是最简单了解和实作的排序算法之一，
                                但它对于少数元素之外的数列排序是很没有效率的。
                                冒泡排序是与插入排序拥有相等的执行时间，但是两种法在需要的交换次数却很大地不同。在最坏的情况，冒泡排序需要次交换，
                                而插入排序只要最多交换。冒泡排序的实现（类似下面）通常会对已经排序好的数列拙劣地执行（），而插入排序在这个例子只需要个运算。
        @param arr待排序数组
        */
        public static void bubbleSort(int [] arr)
        {
                for (int i=0; i<arr.length-1;i++)
                {
                        for (int j=0;j<arr.length-i-1;j++)
                        {
                                if(arr[j+1] > arr[j])
                                {
                                        arr[j+1] = arr[j+1]^arr[j];
                                        arr[j] = arr[j+1]^arr[j];
                                        arr[j+1] = arr[j+1]^arr[j];
                                }
                        }
                }
        }
       
        /**
        完成插入排序
        原理：通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
        步骤：
                从第一个元素开始，该元素可以认为已经被排序
                取出下一个元素，在已经排序的元素序列中从后向前扫描
                如果该元素（已排序）大于新元素，将该元素移到下一位置
                重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
                将新元素插入到该位置后
                重复步骤2~5
        复杂度分析：
                                插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，
                                需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。
        */
        public static void insertSort(int arr[])
        {
                for (int i=1;i<arr.length;i++ )
                {
                        int key = arr[i];
                        int position = i;

                        while (position > 0 && arr[position-1]>key)
                        {
                                arr[position] = arr[position-1];
                                position --;
                        }
                        arr[position] = key;
                }
        }
       
        /**
        完成快速排序
        原理：快速排序使用分治法（Divide and conquer）策略来把一个串行（list）分为两个子串行（sub-lists）。
        步骤为：
                从数列中挑出一个元素，称为 "基准"（pivot），
                重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。
                在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。
                递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。
                递归的最底部情形，是数列的大小是零或一，也就是永远都已经被排序好了。虽然一直递归下去，
                但是这个算法总会退出，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。
        复杂分析：在平均状况下，排序 n 个项目要Ο(n log n)次比较。在最坏状况下则需要Ο(n2)次比较，
                          但这种状况并不常见。事实上，快速排序通常明显比其他Ο(n log n) 算法更快，
                           因为它的内部循环（inner loop）可以在大部分的架构上很有效率地被实现出来。
        */
        public static void quickSort(int [] arr,int low, int high)
        {       
                int pivot;
                if (low < high)
                {
                        pivot = getCurrent(arr,low,high);
                        quickSort(arr,low,pivot-1);
                        quickSort(arr,pivot+1,high);
                }
        }
       
        /**
        快排的划分
        做法
　　第一步：(初始化)设置两个指针i和j，它们的初值分别为区间的下界和上界，即i=low，i=high；
                        选取无序区的第一个记录R[i](即R[low])作为基准记录，并将它保存在变量pivot中；
　　第二步：令j自high起向左扫描，直到找到第1个关键字小于pivot.key的记录R[j]，
                        将R[j])移至i所指的位置上，这相当于R[j]和基准R[i](即pivot)进行了交换，
                        使关键字小于基准关键字pivot.key的记录移到了基准的左边，交换后R[j]中相当于是pivot；
                        然后，令i指针自i+1位置开始向右扫描，直至找到第1个关键字大于pivot.key的记录R[i]，
                        将R[i]移到i所指的位置上，这相当于交换了R[i]和基准R[j]，使关键字大于基准关键字的记录移到了基准的右边，
                        交换后R[i]中又相当于存放了pivot；接着令指针j自位置j-1开始向左扫描，如此交替改变扫描方向，
                        从两端各自往中间靠拢，直至i=j时，i便是基准pivot最终的位置，将pivot放在此位置上就完成了一次划分。
        */
        public static int getCurrent(int [] arr, int low, int high)
        {
                int pivot = arr[low];
                while (low < high )
                {
                        while (low<high && arr[high] >= pivot)
                        {
                                high--;
                        }
                        if (low < high)
                        {
                                arr[low++] = arr[high];
                        }
                        while (low < high && arr[low] <= pivot)
                        {
                                low ++;
                        }
                        if (low < high)
                        {
                                arr[high--] = arr[low];
                        }
                }
                //arr[low] = pivot;
                arr[high] = pivot;
                return low;
        }

        /**

        完成数组的打印功能
        */
        public static void printArray(int [] arr)
        {
                System.out.print("[");
                for(int i=0; i<arr.length; i++)
                {
                        if( i != arr.length-1 )
                        {
                                System.out.print(arr[i]+", ");
                        }
                        else
                        {
                                System.out.println(arr[i]+"]");
                        }
                }
        }
}

当时 学习时的小练习，你可以看一下