publicstaticvoidInsertSort(int[] array) { //从下标为1的元素开始选择合适的位置插入,因为下标为0的只有一个元素,默认是有序的 for (int i = 1; i < array.Length; i++) { //记录要插入的数据 int tmp = array[i];
// 归并 privatestaticvoidSort(int[] array, int first, int last, int[] tmp) { if (first < last) { int mid = (first + last) / 2; Sort(array, first, mid, tmp); // 递归归并左边元素 Sort(array, mid + 1, last, tmp); // 递归归并右边元素 MergeArray(array, first, mid, last, tmp); // 再将二个有序数列合并 } }
privatestaticvoidMergeArray(int[] array, int first, int mid, int last, int[] tmp) { int i = first, j = mid + 1; // i为第一组的起点, j为第二组的起点 int m = mid, n = last; // m为第一组的终点, n为第二组的终点 int k = 0; // k用于指向temp数组当前放到哪个位置 // 将两个有序序列循环比较, 填入数组temp
while (i <= m && j <= n) { if (array[i] <= array[j]) tmp[k++] = array[i++]; else tmp[k++] = array[j++]; }
// 如果比较完毕, 第一组还有数剩下, 则全部填入temp while (i <= m) { tmp[k++] = array[i++]; }
publicstaticvoidHeapSort(int[] arr) { int len = arr.Length;
BuildMaxHeap(arr, len);
for (int i = len - 1; i > 0; i--) { Swap(arr, 0, i);//把堆首(最大值)和堆尾互换 len--;//把堆的尺寸缩小 1 Heapify(arr, 0, len);//堆化,把新的最大值移动到堆首 } }
//构建最大堆 privatestaticvoidBuildMaxHeap(int[] arr, int len) { for (int i = (len / 2); i >= 0; i--)//只需要扫描数组的一半元素,因为可以跳过大小为1的之堆 { Heapify(arr, i, len); } }
//堆化 privatestaticvoidHeapify(int[] arr, int i, int len) { int left = 2 * i + 1;//左节点 int right = 2 * i + 2;//右节点 int largest = i;//父节点
//当左节点大于父节点 if (left < len && arr[left] > arr[largest]) { largest = left; }
//当右节点大于父节点 if (right < len && arr[right] > arr[largest]) { largest = right; }
//若最大值不是父节点时 if (largest != i) { //最大值与父节点交换位置 Swap(arr, i, largest); Heapify(arr, largest, len); } }
privatestaticvoidSwap(int[] arr, int i, int j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; }