2013-01-23

 摘要：内部排序,包括直接插入、冒泡、快速、简单选择，堆排序。

1 插入排序

 基本思想：将一个记录插入到以排好序的有序表中，从而得到一个新的、记录数增1的有序表。

1.1 直接插入排序

 

图1 直接插入排序

1 public static void InsertSort(int[] arr) 2         { 3             int i, j; 4             int temp; 5             for (i = 1; i < arr.Length; i++) 6             { 7                 temp = arr[i]; 8                 for (j = i - 1; j >= 0 && temp < arr[j]; j--) 9                 {10                     arr[j + 1] = arr[j];11                 }12                 arr[j + 1] = temp;13             }14         }

2 快速排序

 快速排序时基于“交换”进行排序的方法。

2.1 冒泡排序

 基本思想：1）第一个和第二个比较，若逆序（First>Second），交换。然后进行第二个和第三个，以此类推，直到n-1和n个。这样，第一轮就把最大的“沉”到“底部”。

               2）然后，第二轮比较前n-1个就行，以此类推，得到有序表。

 

图2 冒泡排序

1 //采用自上向下扫描 2         public static void BubbleSort(int[] arr) 3         { 4             int i, j; 5             int temp; 6             for (i = arr.Length - 1; i > 0; i--) 7             { 8                 for (j = 0; j < i; j++) //对当前无序区R[0..n-i]自下向上扫描 9                 {10                     if (arr[j] > arr[j + 1])11                     {12                         temp = arr[j + 1];13                         arr[j + 1] = arr[j];14                         arr[j] = temp;15                     }16                 }17             }18         }

2.2 快速排序

 基本思想：1）通过一趟排序把待排记录分割成独立的两部分，前一部分都比某个记录效，后一部分都比某个记录大

　　　　　 2）对前一部分和后一部分按1）再分区，直到整个序列有序。

图3 快速排序

1 public static void QuickSort(int[] arr) 2         { 3             QSort(arr, 0, arr.Length - 1); 4         } 5  6         public static void QSort(int[] arr, int low, int high) 7         { 8             if (low < high) 9             {10                 int pivotLoc = Partition(arr, low, high);11                 QSort(arr, low, pivotLoc - 1);12                 QSort(arr, pivotLoc + 1, high);13             }14         }15 16         public static int Partition(int[] arr, int low, int high)17         {18             int pivot = arr[low];19             while (low < high)20             {21                 while ((high > low) && arr[high] >= pivot) --high;22                 arr[low] = arr[high];23                 while ((low < high) && (arr[low] <= pivot)) ++low;24                 arr[high] = arr[low];25             }26             arr[low] = pivot;27             return low;28         }

 

3 选择排序

基本思想：每一趟在最后的n-i+1（i=1,2,...,n-1）中取最小的记录作为有序表的第i个记录。

3.1 简单选择排序

 

图4 简单选择排序

1 public static void SelectSort(int[] arr) 2         { 3             int i, j; 4             int minLoc; 5             int temp; 6             for (i = 0; i <= arr.Length - 1; i++) 7             { 8                 minLoc = i; 9 10                 for (j = i + 1; j <= arr.Length - 1; j++)11                     if (arr[j] < arr[minLoc]) minLoc = j;12 13                 if (minLoc != i)14                 {15                     temp = arr[i];16                     arr[i] = arr[minLoc];17                     arr[minLoc] = temp;18                 }19             }20         }

 

3.2 堆排序

堆的定义

图5 堆的定义

我们可以吧这个序列看成一个二叉树，可得， 1）最大堆的根节点最大，2)上层总比下层大

 

1 public static void HeapSort(MyArr arr) 2         { 3             int i; int r; 4             for (i = arr.Length / 2; i > 0; --i) 5             {  //把H.r[1...H.length]建成大顶堆 6                 HeapAdjust(arr, i, arr.Length - 1); 7             } 8             for (i = arr.Length; i > 1; --i) 9             {10                 //将堆顶记录和当前未经排序子序列H.r[1..i]中最后一个记录相互交换11                 r = arr[1]; arr[1] = arr[i]; arr[i] = r;12                 HeapAdjust(arr, 1, i - 1);  //将H.r[1..i-1]重新调整为大顶堆13             }14         }15 16         //小的放在下层17         public static void HeapAdjust(MyArr arr, int s, int m)18         {19             int rc = arr[s];20             for (int j = 2 * s; j <= m; j = 2 * j)21             {  //沿key较大的孩子结点向下筛选22                 if (j < m && arr[j] < arr[j + 1]) ++j; //j为key较大的记录的下标23                 if (rc >= arr[j]) break; //rc应插入在位置s上24                 arr[s] = arr[j]; s = j;25             }26             arr[s] = rc;   //插入27         }28 29         //因为以零开始的数组，对于堆栈不好操作，也容易误解，所以自定义数组，以1起始30         public class MyArr31         {32             int[] arr;33             public int this[int pos]34             {35                 get36                 {37                     return arr[pos - 1];38                 }39                 set40                 {41                     arr[pos - 1] = value;42                 }43             }44             public int Length45             {46                 get47                 {48                     return arr.Length;49                 }50             }51             public MyArr(int[] arr)52             {53                 this.arr = arr;54             }55         }

4 客户端 

1 class Program 2     { 3         static void Main(string[] args) 4         { 5             //1 直接插入排序 6             int[] sample = new int[] { 53, 27, 36, 15, 69, 42 }; 7             DisplayArray("Original Sequence is: ", sample); 8             Sort.InsertSort(sample); 9             DisplayArray("InsertSort Sequence is: ", sample);10             //2 冒泡排序11             sample = new int[] { 70, 30, 40, 10, 80, 20, 90, 100, 75, 60, 45 };12             DisplayArray("Original Sequence is: ", sample);13             Sort.BubbleSort(sample);14             DisplayArray("BubbleSort Sequence is: ", sample);15             //3 快速排序16             sample = new int[] { 49, 38, 65, 97, 76, 13, 27 };17             DisplayArray("Original Sequence is: ", sample);18             Sort.QuickSort(sample);19             DisplayArray("QuickSort Sequence is: ", sample);20             //4 简单选择排序21             sample = new int[] { 58, 23, 35, 10, 76, 12 };22             DisplayArray("Original Sequence is: ", sample);23             Sort.SelectSort(sample);24             DisplayArray("SelectSort Sequence is: ", sample);25             //5 堆排序26             Sort.MyArr arr = new Sort.MyArr(new int[] { 49, 38, 65, 97, 76, 13, 27, 49 });27             Console.Write("Original Sequence is: ");28             for(int m=1;m

 

5 各种内部排序比较

排序方法	平均情况	最坏情况	辅助空间
直接插入排序	O(n2)	O(n2)	O(1)
起泡排序	O(n2)	O(n2)	O(1)
快速排序	O(nlogn)	O(n2)	O(logn)
简单选择排序	O(n2)	O(n2)	O(1)
堆排序	O(nlogn)	O(nlogn)	O(1)