1. 插入排序（Insertion Sort）
算法的复杂度也是简单的，排序第一个需要1的复杂度，排序第二个需要2的复杂度，因此整个的复杂度就是
1 + 2 + 3 + …… + N = O（N ^ 2）的复杂度。
// 插入排序 void InsertSort( int array[], int length) { int i, j, key; for (i = 1; i < length; i++) { key = array[i]; // 把i之前大于array[i]的数据向后移动 for (j = i - 1; j >= 0 && array[j] > key; j--) { array[j + 1] = array[j]; } // 在合适位置安放当前元素 array[j + 1] = key; } }
|
|
static void InsertSort( int[] array, int length) { for ( int i = 1; i < length; i++) { int temp = array[i]; int tempIndex = i; for ( int j = i - 1; j >= 0 && array[j] > temp; j--) { array[j + 1] = array[j]; tempIndex = j; } array[tempIndex] = temp; } }
2. 冒泡排序 （bubble sort）
将被排序的记录数组R[1..n]垂直排列，每个记录R[i]看作是重量为R[i].key的气泡。根据轻气泡不能在重气泡之下的原则，从下往上扫描数组R：凡扫描到违反本原则的轻气泡，就使其向上"飘浮"。如此反复进行，直到最后任何两个气泡都是轻者在上，重者在下为止。
（1）初始 R[1..n]为无序区。（2）第一趟扫描 从无序区底部向上依次比较相邻的两个气泡的重量，若发现轻者在下、重者在上，则交换二者的位置。即依次比较(R[n]，R[n-1])，(R[n-1]，R[n-2])，…，(R[2]，R[1])；对于每对气泡(R[j+1]，R[j])，若R[j+1].key<R[j].key，则交换R[j+1]和R[j]的内容。 第一趟扫描完毕时，"最轻"的气泡就飘浮到该区间的顶部，即关键字最小的记录被放在最高位置R[1]上。（3）第二趟扫描 扫描R[2..n]。扫描完毕时，"次轻"的气泡飘浮到R[2]的位置上…… 最后，经过n-1 趟扫描可得到有序区R[1..n] 注意： 第i趟扫描时，R[1..i-1]和R[i..n]分别为当前的有序区和无序区。扫描仍是从无序区底部向上直至该区顶部。扫描完毕时，该区中最轻气泡飘浮到顶部位置R[i]上，结果是R[1..i]变为新的有序区。
static void Main( string[] args) { int[] array = { 23, 45, 16, 7, 42 }; int length = array.Length - 1; bool isExchanged = false; for ( int i = 0; i < length; i++) { isExchanged = false; for ( int j = length; j > i; j--) { if (array[j] > array[j - 1]) { int temp = array[j]; array[j] = array[j - 1]; array[j - 1] = temp; isExchanged = true; } } if (!isExchanged) // 一遍比较过后如果没有进行交换则退出循环 { break; } } foreach ( int i in array) { Console.WriteLine(i); } Console.Read(); }
3.快速排序 （Quick Sort)
private static void Sort( int[] numbers, int left, int right) { // 左边索引小于右边，则还未排序完成 if (left < right) { // 取中间的元素作为比较基准，小于他的往左边移，大于他的往右边移 int middle = numbers[(left + right) / 2]; // int i = left - 1; // int j = right + 1; int i = left; int j = right; while ( true) { while (i < right && numbers[i] < middle) { i++; }; while (j > 0 && numbers[j] > middle ) { j--; }; if (i >= j) { break; } Swap(numbers, i, j); } Sort(numbers, left, i - 1); Sort(numbers, j + 1, right); } } /// <summary> /// 交换元素值 /// </summary> /// <param name="numbers"> ；数组 </param> /// <param name="i"> ；当前左边索引 </param> /// <param name="j"> ；当前右边索引 </param> /// private static void Swap( int[] numbers, int i, int j) { int number = numbers[i]; numbers[i] = numbers[j]; numbers[j] = number; } }
4. 直接选择排序 (Straight Selection Sort)
private static void QuitSort( int[] numbers, int length) { for ( int i = 0; i < length - 1; i++) { int temp = i; for ( int j = i + 1; j < length; j++) { if (numbers[j] < numbers[temp]) { temp = j; } } if (temp != i) { Swap(numbers, i, temp); } } }
5. 堆排序 (Heap Sort)
1）。用迭代实现堆排序
/// <summary> /// 建立最大堆 /// </summary> /// <param name="arr"></param> /// <param name="i"></param> /// <param name="length"></param> static void HeapAdjust( int[] arr, int i, int length) { int child = 2 * i + 1; // 左节点 int temp = arr[i]; // 中间变量保存当前根节点 while (child < length) { // 如果有右节点，判断是否大于左节点 if (child < length - 1 && arr[child] < arr[child + 1]) child++; // 双亲节点大于子节点 if (temp >= arr[child]) break; // 不需调整，结束调整 arr[i] = arr[child]; // 双亲结点值设置为大的子节点值,将节点子付给父节点。 i = child; child = 2 * i + 1; // 如果这个节点本身还有子节点，继续往下调整。类似于递归的原理。 } arr[i] = temp; // 找到最后一个交换点，赋值。如果没有交换，付给开始的父节点。否则，赋值给最后一个进行交换的子节点。 } public static void Heap( int[] arr) { // 第一次创建大堆 for ( int i = arr.Length / 2 - 1; i >= 0; i--) { // 从后面的subtree开始保证每个tree都是堆 HeapAdjust(arr, i, arr.Length); } // 元素位置调换 for ( int i = arr.Length - 1; i > 0; i--) { // 堆顶与当前堆的最后一个堆元素交换位置，把最大的值放到最后。 int tmp = arr[ 0]; arr[ 0] = arr[i]; arr[i] = tmp; // 将剩下的无序堆部分重新建堆处理 HeapAdjust(arr, 0, i); foreach ( int v in arr) { Console.Write(v.ToString() + " "); } Console.WriteLine( ""); } }
2）.利用递归实现堆排序
/// <summary> /// 建立最大堆 /// </summary> /// <param name="arr"></param> /// <param name="i"></param> /// <param name="length"></param> static void HeapAdjust( int[] arr, int i, int length) { if ( 2 * i + 1 < length) { int child = 2 * i + 1; // 左节点 int temp = arr[i]; if (child < length - 1 && arr[child] < arr[child + 1]) child++; // 双亲节点大于子节点 if (temp >= arr[child]) return; // 不需调整，结束调整 arr[i] = arr[child]; // 双亲结点值设置为大的子节点值,将节点子付给父节点。 i = child; HeapAdjust(arr, 2 * child + 1, length); arr[i] = temp; } // 找到最后一个交换点，赋值。如果没有交换，付给开始的父节点。否则，赋值给最后一个进行交换的子节点。 } public static void Heap( int[] arr) { // 第一次创建大堆 for ( int i = arr.Length / 2 - 1; i >= 0; i--) { // 从后面的subtree开始保证每个tree都是堆 HeapAdjust(arr, i, arr.Length); } // 元素位置调换 for ( int i = arr.Length - 1; i > 0; i--) { // 堆顶与当前堆的最后一个堆元素交换位置，把最大的值放到最后。 int tmp = arr[ 0]; arr[ 0] = arr[i]; arr[i] = tmp; // 将剩下的无序堆部分重新建堆处理 HeapAdjust(arr, 0, i); foreach ( int v in arr) { Console.Write(v.ToString() + " "); } Console.WriteLine( ""); } }
6. 归并排序（Merge Sort)
static void Merge( int[] a, int low, int mid, int high) { int k = 0; int begin1 = low; int end1 = mid; int begin2 = mid + 1; int end2 = high; int[] b = new int[high - low + 1]; while (begin1 <= end1 && begin2 <= end2) { if (a[begin1] <= a[begin2]) { b[k++] = a[begin1++]; } else { b[k++] = a[begin2++]; } } if (begin1 <= end1) { for ( int q = begin1; q <= end1; q++) { b[k++] = a[q]; } } else { for ( int q = begin2; q <= end2; q++) { b[k++] = a[q]; } } for ( int i = 0; i < b.Length; i++) { a[low++] = b[i]; } // 此步骤相当于在数组a内进行了局部排序。 } static void MergeSort( int[] R, int low, int high) { // 用分治法对R[low..high]进行二路归并排序 int mid; if (low < high) { // 区间长度大于1 mid = (low + high) / 2; // 分解 MergeSort(R, low, mid); // 递归地对R[low..mid]排序 MergeSort(R, mid + 1, high); // 递归地对R[mid+1..high]排序 Merge(R, low, mid, high); // 组合，将两个有序区归并为一个有序区 } }
7. 箱排序 （Bin Sort）
8. 桶排序 （Bucket Sort）