排序算法之选择排序、冒泡排序、快速排序(C#)

打算学习一下排序算法，记录一下方便以后复习。首先介绍一下不同种类的排序算法的复杂度

排序法最差时间分析平均时间复杂度稳定度空间复杂度冒泡排序O(n2)O(n2)稳定O(1)快速排序O(n2)O(n*log2n)不稳定O(log2n)~O(n)选择排序O(n2)O(n2)稳定O(1)二叉树排序O(n2)O(n*log2n)不稳定O(n)插入排序O(n2)O(n2)稳定O(1)堆排序O(n*log2n)O(n*log2n)不稳定O(1)希尔排序OO不稳定O(1)

选择排序

选择排序，两次for循环，遍历数组，最外层的for循环假选定i为最小值的下标。下层for循环遍历数组，找到最小的下表。对元素交换。继续遍历，这就是选择排序。选择排序菜鸟教程链接 下面是菜鸟教程的动态图，我直接引用了。 下面是选择排序的C#代码

/// <summary> /// 选择排序 /// </summary> /// <param name="nums"></param> /// <returns></returns> public int[] selectSort(int[] nums) { for (int i = 0; i < nums.Length; i++) { int minVal = i; for (int j = i + 1; j < nums.Length; j++) { if (nums[j]<nums[i]) { minVal = j; } } if (i!=minVal) { int temp = nums[i]; nums[i] = nums[minVal]; nums[minVal] = temp; } } return nums; }

冒泡排序

同样两个for循环，比较前后两个数字大小，按所需排序交换前后两个数字。 C#代码如下

/// <summary> /// 冒泡排序 /// </summary> /// <param name="nums"></param> public void BubbleSort(int[] nums) { for (int i = 0; i < nums.Length-1; i++) { for (int j = 0; j < nums.Length-1-i; j++) { if (nums[i]<nums[j]) { int temp = nums[j]; nums[j] = nums[i]; nums[i] = temp; } } } }

快速排序

将数组中的一个元素，该元素为基准，大于该元素放在右侧，小于该元素放在左侧。之后对该基准元素左侧、右侧按同样方式递归。 代码如下

/// <summary> /// 快速排序 /// </summary> /// <param name="nums">数组</param> /// <param name="l">数组排序开始位置</param> /// <param name="r">排序结束位置</param> public void QuickSort(int[] nums, int l, int r) { //数组为空结束(特殊情况判断) if (nums == null || nums.Count() == 0) { return; } //右侧大于左侧结束 if (l >= r) { return; } //调用一次 排序 并查找基准值位置 int pivot = sortOnce(nums, l, r); //递归 QuickSort(nums, l, pivot - 1); QuickSort(nums, pivot + 1, r); } public int sortOnce(int[] nums, int left, int right) { //以最左侧为基准 int pivot = nums[left]; while (left < right) { //右侧开始循环 存在小于,就赋值给左侧 while (nums[right] >= pivot && left < right) { right--; } nums[left] = nums[right]; while (nums[left] <= pivot && left < right) { left++; } nums[right] = nums[left]; } //基准值赋值回数组 并返回基准位置 nums[left] = pivot; return left; }