排序算法

参考博客

• 十大经典排序算法
• 八大排序算法稳定性分析，原来稳定性是这个意思…

算法稳定性

• 排序前后两个相等的数相对位置不变，则算法稳定

冒泡排序

1. 小的元素往前调或者把大的元素往后调；
2. 比较是相邻的两个元素比较，交换也发生在这两个元素之间；
3. 稳定排序算法
4. 排序遍历次数为len - 1，每次从头开始冒泡
   • 示例代码

     template<typename T> //整数或浮点数皆可使用,若要使用类(class)或结构体(struct)时必须重载大于(>)运算符
     void bubble_sort(T arr[], int len) {
             int i, j;
             for (i = 0; i < len - 1; i++)
                     for (j = 0; j < len - 1 - i; j++)
                             if (arr[j] > arr[j + 1])
                                     swap(arr[j], arr[j + 1]);
     }

快速排序

1. 选定的piviot必须位于开始排序的起始位置；即使选中间某个数，也要将其交换至起始位置才能开始排序
2. 考虑==占空==来识记算法排序的过程
   • 判断起始序号 < 结尾序号
   • 第一个空位在起始位置，i
   • 从右边找第一个小于piviot的元素，占据已有的空位；此时形成新的空位在右侧，j
   • 接着从左边开始找第一个大于piviot的元素，占据前述空位；此时形成新的空位在左侧
   • 重复上述查找，直至==i >= j==
   • 最后，将piviot的值放在空位上
   • 对左序列、右序列进行递归操作

     class Solution {
     
     public:
     
     	void dfs(vector<int>& nums, int start, int end)
     	{
     	
     		if (start >= end) return;
     		swap(nums[start], nums[(start+end)/2]);
     		int piviot = nums[start];
     		int i = start, j = end;
     		while (i < j)
     		{
     			while (i < j && nums[j] >= piviot) --j;
     			nums[i] = nums[j];
     			while (i < j && nums[i] <= piviot) ++i;
     			nums[j] = nums[i];
     		}
     		nums[i] = piviot;
     		dfs(nums, start, i-1);
     		dfs(nums, i+1, end);
     	}
     
     	vector<int> sortArray(vector<int>& nums)
     	{
     		dfs(nums, 0, nums.size()-1);
     		return nums;
     	}
     
     };