8 内部排序

1 交换类排序

　　通过一系列交换逆序元素进行排序。

1.1 冒泡排序

 1 public void BubbleSort(int[] arr, int n){
 2     boolean change = true;
 3     for(int i = 1; i <= n - 1 && change; i++){
 4         change = false;
 5         for(int j = 0; j < n - i; j++){
 6            if(arr[j] > arr[j + 1]){
 7               int t = arr[j];
 8               arr[j] = arr[j + 1];
 9               arr[j + 1] = t;
10               change = true;     
11            }
12         }
13     }
14 }
15 
16 int[] num = {48, 62, 35, 77, 55, 14, 35, 98, 22, 40};

冒泡排序

1.2 快速排序

　　消除多个逆序。

 1     public void QKSort(int[] a, int low, int high)
 2     /* 对数组 a[low.. high] 进行快速排序*/
 3     {
 4        if(low < high)
 5        {
 6            int pos = QKPass(a, low, high);  /* 调用一趟快速排序，以枢轴元素为界划分两个子表 */
 7            QKSort(a, low, pos - 1);  /* 对左部子表快速排序 */
 8            QKSort(a, pos + 1, high);  /* 对右部子表快速排序 */
 9        }  
10     }
11 
12     public int QKPass(int[] a, int low, int high)
13     {
14         int x = a[low];  /* 选择基准记录 */
15         while(low < high)
16         {
17             while(low < high && x <= a[high])  /* high从右到左找小于x的记录，此时a[low]相当于空单元 */
18                 high--;
19             if(low < high)
20             {
21                 a[low] = a[high];  /* 此时a[high]相当于空单元 */
22                 low++;
23             }
24             while(low < high && x > a[low])  /* low从左到右找大于x的记录 */
25                 low++;
26             if(low < high)
27             {
28                 a[high] = a[low];
29                 high--;
30             }
31         }
32         a[low] = x;  /* 将基准记录保存到 low = high 的位置 */
33         return low;  /* 返回基准记录的位置 */
34     }
35     
36     int[] a = {48, 62, 35, 77, 55, 14, 35, 98};

快速排序

2 选择类排序

　　每一趟在 n - i + 1 个记录中选取关键字最小的记录作为有序序列中第 i 个记录。

2.1 简单选择排序

 1 public static void SelectSort(int[] a, int n)
 2 {
 3     for(int i = 0; i < n; i++)  /* 经过 n - 1 趟简单选择排序 */
 4     {
 5         int k = i;
 6         for(int j = i + 1; j < n; j++)
 7             if(a[k] > a[j])    k = j;
 8         if(k != i)
 9         {
10             int x = a[i];
11             a[i] = a[k];
12             a[k] = x;
13         }
14     }
15 }

简单选择排序

2 基于线性表的查找法

2.1 折半查找

　　① 必须采用顺序存储结构，② 必须按关键字大小有序排列。

 1     public int BinSrch(int[] a, int k)
 2     {
 3         int low = 0;     int high = a.length - 1;  /* 置区间初值 */
 4         while(low <= high)
 5         {
 6             int mid = (low + high) / 2;
 7             if (k == a[mid] )    
 8                 return mid;
 9             else if (k < a[mid])
10                 high = mid - 1;
11             else
12                 low = mid + 1;
13         }
14         
15         return -1;
16     }
17     
18     int[] a = {6, 12, 15, 18, 22, 25, 28, 35, 46, 58, 60};

折半查找