排序算法总结

六大排序

非递归式排序

1.1 选择排序

• 选择排序的核心思想是什么?

  • 选择排序每次选择最小或最大移动到指定最前或最后
  • 然后在排除掉上一轮产生的就绪位的最值后，继续在新的数组上选择最值就绪

• 选择排序和冒泡排序的区别在哪里？

  • 冒泡排序是每次左右比较“冒泡”进行移动到指定位置，发生多次交换
  • 选择排序是每次选出最值，直接移动到指定位置，发生一次交换，两者比较次数相同，交换次数不同

• 代码实现

  // 选择排序 
  #include<iostream>
  
  using namespace std;
  const int N = 1e5+10000;
  
  void selectionsort(int a[], int l ,int r)
  {
  	int max = 0;
  	for(int i = r; i >= l; i--)
  	{
  		max = 0;
  		for(int j = l; j <= i; j++)
  		{
  			if(a[j]>a[max])max = j;
  		}
  		swap(a[max],a[i]);
  	}
  }
  
  int main()
  {
  	int n, a[N];
  	scanf("%d", &n);
  	for(int i = 0; i < n; i++)scanf("%d", &a[i]);
  	selectionsort(a, 0, n-1);
  	for(int i = 0; i < n; i++)printf("%d ", a[i]);
  	return 0;
   }
  

1.2 冒泡排序

• 冒泡排序的核心思想是什么？

  • 冒泡排序是每次进行左右比较不断的将最值，送到指定位置
  • 在排除上一轮最值后继续挑选最值，通过冒泡将最值送到指定位置

• 代码实现

  // 冒泡排序 
  #include<iostream>
  
  using namespace std;
  const int N = 1e5+10000;
  
  void bubblesort(int a[], int l ,int r)
  {
  	for(int i = r; i >= l; i--)
  	{
  		for(int j = l; j < i; j++)
  		{
  			if(a[j]>a[j+1])swap(a[j],a[j+1]);
  		}
  	}
  }
  
  int main()
  {
  	int n, a[N];
  	scanf("%d", &n);
  	for(int i = 0; i < n; i++)scanf("%d", &a[i]);
  	bubblesort(a, 0, n-1);
  	for(int i = 0; i < n; i++)printf("%d ", a[i]);
  	return 0;
   }
  

1.3 插入排序

• 插入排序的核心思想是什么？

  • 从第二个位置开始每次将选择的元素插入到指定位置
  • 前面数列有序，后面数列无序

• 插入排序和选择排序的区别？

  • 插入排序是不断从无序数列中挑选元素插入到有序数列使其仍然构成有序数列

  • 选择排序是依靠位置顺序每次选择最值使其成为有序数列

  • 插入排序是局部冒泡，交换次数变多，但是和数据相关

  • 时间复杂度都是

    $$O(1)+O(2)+...+O(n?1)=O（n^2)$$

• 代码实现

  // 插入排序 
  #include<iostream>
  
  using namespace std;
  const int N = 1e5+10000;
  
  void insertionsort(int a[], int l ,int r)
  {
  	for(int i = l; i <= r; i++)
  	{
  		for(int j = i; j > l; j--)
  		{
  			if(a[j]<a[j-1])swap(a[j],a[j-1]);
  		}
  	}
  }
  
  int main()
  {
  	int n, a[N];
  	scanf("%d", &n);
  	for(int i = 0; i < n; i++)scanf("%d", &a[i]);
  	insertionsort(a, 0, n-1);
  	for(int i = 0; i < n; i++)printf("%d ", a[i]);
  	return 0;
   }
  

1.4 希尔排序

• 希尔排序的核心思想是什么？

  • 希尔排序是在插入排序上的改进，优化对于数据量不大相对有序的数据的排序过程
  • 指定gap进行分组，在分组中进行插入排序（步进长度为gap
  • 缩小gap，继续进行分组和插入排序
  • 直到gap缩小为1，进行整体插入排序

• 希尔排序和插入排序的区别？

  • 插入排序对于无序的效率更高

  • 希尔排序对于相对有序的数据效率更高，时间复杂度接近于O(n)

  • 总的来说两者时间复杂度都是

    $$O(1)+O(2)+...+O(n?1)=O（n^2)$$

• 代码实现

  // 希尔排序 
  #include<iostream>
  
  using namespace std;
  const int N = 1e5+10000;
  
  void shellsort(int a[], int l ,int r)
  {
  	int len = r-l+1;
  	for(int gap = len>>1; gap > 0; gap >>= 1)
  	{
  		for(int i = gap; i < len; i++)
  		{
  			for (int j = i - gap; j >= 0; j -= gap)
  			{
  				if(a[j]>a[j+gap])swap(a[j],a[j+gap]);
                          
  			}
  		}
  	}
  }
  
  int main()
  {
  	int n, a[N];
  	scanf("%d", &n);
  	for(int i = 0; i < n; i++)scanf("%d", &a[i]);
  	shellsort(a, 0, n-1);
  	for(int i = 0; i < n; i++)printf("%d ", a[i]);
  	return 0;
   }
  

递归式排序

2.1 分而治之

• 分而治之工作原理
  • 1. 如何确定基线条件？
    • 所谓确定基线条件（递归基）就是使递归有一个函数出口，通常为最简单情况，所有递归流程从该处返回
  • 2. 如何不断将问题分解（或者缩小规模）直到符合基线条件？
    • 所谓将问题分解，就是进行递归运算，将原始问题转化为新的子问题
    • 整个递归流程就是不断将原始问题转换为新的子问题，直到转换为最简单的基线条件进行运算，而子问题之间存在关系例如sum递归函数的加法关系，快速排序中数列顺序关系，最后通过关系将子问题整合就可以得到问题的完整解

2.2 快速排序

• 如何运用快速排序算法思想将问题进行分解？

  • 选择基准值pivot
  • 根据基准值将数组划分为两个子数组，即大于基准值的子数组和小于基准值的子数组，并保持数组的相对顺序
  • 分别对子数组进行快速排序
  • 直到问题被分解到基线条件

• 如何确定快速排序的基线条件？

  • 数组排序的基线条件即最简单条件就是不需要排序，即数组为空或仅存在一个元素的时候

• 快速排序在什么时候会退化到O(n2)

  • 如何快速排序树高度为O(n)则快速排序整体时间复杂度会退化到O(n2)
  • 即每次选择的分界点为数组最前端元素，例如原本有序数组进行快速排序

• 快速排序示例

  #include<iostream>
  using namespace std;
  
  const int N = 1e5+10;
  
  int n;
  long long a[N];
  void quick_sort(long long a[], int l, int r)
  {
      if (l >= r) return;
  
      int i = l - 1, j = r + 1, x = a[l + r >> 1];
      while (i < j)
      {
          do i ++ ; while (a[i] < x);
          do j -- ; while (a[j] > x);
          if (i < j) swap(a[i], a[j]);
      }
      quick_sort(a, l, j), quick_sort(a, j + 1, r);
  }
  int main(){
  	scanf("%d", &n);
  	for(int i = 0; i < n; i++)scanf("%d", &a[i]);
  	quick_sort(a, 0, n-1);
  	for(int i = 0; i < n; i++)printf("%lld ", a[i]);
  	return 0;
  }
  

• 快速排序时间复杂度

  ！O(n*logn)

2.3 归并排序

• 如何运用归并排序算法思想将问题进行分解

  • 根据中间元素将数组划分为两个子数组，即该元素前部分数组和包含该元素后部分数组
  • 分别对子数组进行归并排序
  • 直到问题被分解道基线条件
  • 按序合并子数组，组成有序数组返回

• 如何确定归并排序的基线条件

  • 数组/向量排序的基线条件一般都是数组为空或仅存一个元素

• 归并排序和快速排序的区别和联系

  • 归并排序是在合并的时候进行数组的顺序整理然后返回最后实现整体数组有序；快速排序实在划分的时候将子数组按照相对顺序划分，最后实现整体数组有序
  • 归并排序时间复杂度始终是O(nlogn)，快速排序时间复杂度可能会退化到O(n2)
  • 快速排序相对于归并排序来说元素移动次数更少（写内存次数更少），所以快速排序更快

• 归并排序示例

  #include<iostream>
  
  using namespace std;
  
  //#define N 1e5+10
  
  const int N = 1e5+10000;
  
  int tmp[N];
  
  void merge(int a[], int l, int mid, int r)
  {
  	int i = l, j = mid + 1, k = 0;
  	while(i <= mid && j <=r)a[i] > a[j] ? tmp[k++] = a[j++] : tmp[k++] = a[i++];
  	while(i <= mid)tmp[k++] = a[i++];
  	while(j <= r)tmp[k++] = a[j++];
  	for(i = l, j = 0; i <= r; i++, j++)a[i] = tmp[j];
  }
  
  void mergesort(int a[],int l, int r)
  {
  	if(l >= r) return;
  	int mid = l + r >> 1;
  	mergesort(a, l, mid);
  	mergesort(a, mid+1, r);
  	merge(a, l, mid, r);
  }
  
  int main()
  {
  	int n, a[N];
  	scanf("%d", &n);
  	for(int i = 0; i < n; i++)scanf("%d", &a[i]);
  	mergesort(a, 0, n-1);
  	for(int i = 0; i < n; i++)printf("%d ", a[i]);
  	return 0;
   }
  

• 归并排序实践复杂度分析
  ！O(n*logn)