///交换排序/ 1. 冒泡排序
每次把数组中最小的数字排在对应的位置。 (1) 代码
Java:
public class Sort { public static void sort(int[] nums) { for (int i = 0; i < nums.length; i++) { boolean sig = false; for (int j = nums.length - 1; j > 0; j--) { if (nums[j] < nums[j - 1]) { int tem = nums[j - 1]; nums[j - 1] = nums[j]; nums[j] = tem; sig = true; } } if (sig == false) return ; } } }C++:
//第一种最简单的冒泡排序，下面代码将数组数字递增排列； class Solution { public: vector<int> bubbleSort(vector<int> vec) { int size = vec.size(); for (int i = size - 1; i > 0; i--) {//每一次遍历是把遍历到的数字放在下面的循环向上冒泡； for (int j = size - 1; j > 0; j--) {//每一次遍历是一次比较前后大小 if (vec[j] < vec[j - 1]) { swap(vec[j], vec[j - 1]); } } } return vec; } }; //第二种 在判断大小的地方添加本次排序是否有交换的步骤，没有交换说明是递增序列，无须排序，break即可 class Solution { public: vector<int> bubbleSort(vector<int> vec) { int size = vec.size(); bool sp = false;//记录一次从后向前是发生交换; for (int i = size - 1; i > 0; i--) { for (int j = size - 1; j > 0; j--) { if (vec[j] < vec[j - 1]) { swap(vec[j], vec[j - 1]); sp = true; } } if (sp == false) break;//没有交换说明是递增序列break; } return vec; } };(2) 算法性能 时间复杂度：最差情况是数组是倒序的，时间复杂度为O(n^2)。 最好情况是数组是正序的，时间复杂度为O(n)。<遍历一次发现没有交换说明数组是有序的> 平均时间复杂度是O(n^2)。 空间复杂度：原数组操作，空间复杂度为O(1)。 稳定性：只移动后一个比前一个小的，相等的不移动所以稳定性高。
2. 快速排序
1.在待排序的元素任取一个元素作为基准(通常选第一个元素，称为基准元素） 2.将待排序的元素进行分块，比基准元素大的元素移动到基准元素的右侧，比基准元素小的移动到作左侧，从而一趟排序过程，就可以锁定基准元素的最终位置 3.对左右两个分块重复以上步骤直到所有元素都是有序的（递归过程） Java:
public class Sort { public static void quickSort(int[] nums, int l, int r) { int left = l, right = r; if (left >= right) return ; int cmp = nums[l];//注！！基准值是每次给的最左边是参数l； while (left < right) {//注！！边界条件是left<right while (left < right && nums[right] >= cmp) {//注！！需要等于才能越过等于的数； right--;//注！！选择左边基准值就要先从右边开始； } while (left < right && nums[left] <= cmp) { left++; } if (left < right) { int tem = nums[left]; nums[left] = nums[right]; nums[right] = tem; } } int tem = nums[l];//注！！基准归位； nums[l] = nums[left]; nums[left] = tem; quickSort(nums, l, left - 1); quickSort(nums, left + 1, r); } }C++:
class Solution { public: vector<int> quickSort(vector<int> &nums, int left, int right) { if (left >= right) return {};//当例如左边只有一个数字返回，或者右面没有数字返回 int i = left, j = right, cmp = nums[left];//以左边数字作为比较值，就要先移动右边指针 while (i < j) { while (i < j && nums[j] >= cmp) {//j往左移动找比cmp小的值停在这个位置，等于cmp的位置不需要停 j--; } while (i < j && nums[i] <= cmp) {//i往右移动找比cmp大的值停在这个位置，因为有等于号所以cmp点不会停下来，等ij相遇才把cmp交换 i++; } if (i < j) { swap(nums[i], nums[j]); } } swap(nums[i], nums[left]); quickSort(nums, left, i - 1); quickSort(nums, i + 1, right); return nums; } };(2) 算法性能 时间复杂度：最差情况是数组有序，则递归树是偏树，树的深度是n，每层操作的次数是n次，所以时间复杂度是O(n^2)。 最好情况是数组均匀分布，则递归树两边是平衡的，树的深度是logn，每层操作的次数是n次，所以时间复杂度是0(nlogn)。 空间复杂度：操作是对原数组操作的，主要消耗栈空间，即递归树的深度。 稳定性：相等元素可能会因为分区而交换顺序，所以它是不稳定的算法。
///插入排序/
3. 直接插入排序
将第一项作为一个排序序列，后一项往这个数组中插入，数大的就后移 <也可以看成是分段冒泡排序，一开始的数组是一个，加入一个冒泡排序，再加入一个冒泡排序> <每次前面的数组都是有序的，优化可以在插入的时候用二分> (1) 代码
class Solution { public: vector<int> directInsert(vector<int> vec) { for (int i = 1; i < vec.size(); i++) {//从第二个数字开始，这个数字遍历的是数组后面的数字往已经排序的数组中插入 int com = vec[i];//要插入的这个数字 for (int j = i - 1; j >= 0; j--) {//遍历已经排序的数组往其中插入 if (com < vec[j]) {//要插入的数字com只要比已经排序的数组中遍历到的这个数字小，就把排序数组中的这个数字后移 swap(vec[j+ 1], vec[j]); } } } return vec; } };(2) 算法性能 时间复杂度：最差情况是数组倒叙，先遍历数组，每次插入都需要移动前面的元素，时间复杂度为O(n^2)。 最好情况是数组正序，只需遍历一次，每次插入不需要移动前面的元素，时间复杂度为O(n)。 平均是O(N^2)。 稳定性：只移动比较小的，相等的不移动所以稳定。
///选择排序/
4. 堆排序 堆：父节点大于子节点的完全二叉树。 Java:
public class Sort { public static void heapSort(int[] nums) { for (int i = 0; i < nums.length; i++) { heapInsert(nums, i); } for (int i = nums.length - 1; i >= 0; i--) { int tem = nums[0]; nums[0] = nums[i]; nums[i] = tem; heapify(nums, 0, i); } } public static void heapInsert(int[] nums, int idx) { int far = (idx - 1) / 2; while (nums[idx] > nums[far]) { int tem = nums[idx]; nums[idx] = nums[far]; nums[far] = tem; idx = far; far = (far - 1) / 2; } } public static void heapify(int[] nums, int far, int heapSize) { while (far < heapSize) { int lefChild = 2 * far + 1, rigChild = 2 * far + 2; int max = far; if (lefChild < heapSize && nums[lefChild] > nums[max])//注！！与max比较！ max = lefChild;//注！！max、far都是下标，比较的是数字； if (rigChild < heapSize && nums[rigChild] > nums[max]) max = rigChild; if (max == far) break;//注！！父节点没有变中断循环 else { int tem = nums[max]; nums[max] = nums[far]; nums[far] = tem; far = max; } } } }Cpp:
class Solution { public: void heapSort(vector<int> &nums) { for (int i = 0; i < nums.size(); i++) { heapInsert(nums, i); } for (int i = nums.size() - 1; i >= 0; i--) { swap(nums[0], nums[i]);//注！！每次都要把最大值交换后再heapify heapify(nums, 0, i);//注！！i表示heapSize } } private: void heapInsert(vector<int> &nums, int index) { int far = (index - 1) / 2; while (nums[index] > nums[far]) {//注！！往上走far不会越界； swap(nums[far], nums[index]); index = far; far = (far - 1) / 2;//注！！far是往上走的，所以不会超过0； } //判断条件index和far相等时可以停止； } void heapify(vector<int> &nums, int far, int heapSize) { while (far <= heapSize - 1) {//注！！往下走far需要考虑越界； int left = 2 * far + 1, right = 2 * far + 2; int max = far; if (left <= heapSize - 1 && nums[left] > nums[max]) {//注！！与max比较 max = left;//注！！max只用来标记 } if (right <= heapSize - 1 && nums[right] > nums[max]) { max = right; } if (max == far) {//注！！== break; //注！！之前如果far就是max或者左或右节点越界了都不需要继续往下了 } else { swap(nums[max], nums[far]); far = max; } } } };(2) 算法性能 时间复杂度：heapInsert(建堆)的时间复杂度是O(n) <每加入一个节点之和二叉树层数有关:log1 + log2 + … + logN - 1> heapify(调整为堆)的时间复杂度是O(nlogn) <一共heapify n次，每次只与一条路径相关> 综上时间复杂度是O(nlogn) 稳定性：相等元素可能会被交换位置，所以是不稳定的。
///归并排序/ 5. 归并排序 分解（Divide）：将n个元素分成个含n/2个元素的子序列。 解决（Conquer）：用合并排序法对两个子序列递归的排序。 合并（Combine）：合并两个已排序的子序列已得到排序结果。
java:
public class Sort<kClosest> { public void mergeSort(int[] nums, int left, int right) { if (left >= right) return ; int middle = left + (right - left) / 2; mergeSort(nums, left, middle); mergeSort(nums, middle + 1, right); merge(nums, left, middle, right); } public void merge(int[] nums, int left, int middle, int right) { int[] tem = new int[right - left + 1]; int p1 = left, p2 = middle + 1; int i = 0;//先填tem while (p1 <= middle && p2 <= right) { tem[i++] = nums[p1] < nums[p2] ? nums[p1++] : nums[p2++]; } while (p1 <= middle) {//两个while只发生一个 tem[i++] = nums[p1++]; } while (p2 <= right) { tem[i++] = nums[p2++]; } //再填nums for (i = 0; i < tem.length; i++) { nums[left + i] = tem[i];//注！！是left + i; } } }