数据结构：排序解析

文章目录

• 前言
• 一、常见排序算法的实现
• • 1.插入排序
  • • 1.直接插入排序
    • 2.希尔排序
    • 2.交换排序
    • • 1.冒泡排序
      • 2.快速排序
      • • 1.hoare版
        • 2.挖坑版
        • 3.前后指针版
        • 4.改进版
        • 5.非递归版
        • 3.选择排序
        • • 1.直接选择排序
          • 2.堆排序
          • 4.归并排序
          • • 1.归并排序递归实现
            • 2.归并排序非递归实现
            • 5.计数排序
            • 二、排序算法复杂度及稳定性
            • 排序测试

              前言

              所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。排序在我们生活中非常常见，比如买东西看的销量，价格的对比等。排序也分为内部排序和外部排序。内部排序是数据元素全部放在内存中的排序，外部排序则是数据元素太多不能同时放在内存中，根据排序过程的要求不能在内外存之间移动数据的排序。下面让我们正式认识排序吧。

              一、常见排序算法的实现

              1.插入排序

              把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列。

              1.直接插入排序

              void  InsertSort(int* nums, int numsSize)
              {
              	int i = 0;
              	//i变量控制的是整个比较元素的数量
              	for (i = 0; i  -1)
               		{
               			if (nums[j] > num)
               			{
              				//要交换的元素小于前一个元素
               				nums[j + 1] = nums[j];
               				j--;
               			}
               			else
               			{
               				break;
               			}
               		}
              		//把该元素填到正确的位置
               		nums[j + 1] = num;
              	}
              }
              

              

              测试用例：

              void sortArray(int* nums, int numsSize)
              {
              	InsertSort(nums, numsSize);//插入排序
              }
              void print(int* nums, int numsSize)
              {
              	int i = 0;
              	for (i = 0; i  
              直接插入排序的优点：元素集合越接近有序，直接插入排序算法的时间效率越高。 
               时间复杂度：O（N ^2）
               空间复杂度O（1）
              直接插入排序是一种稳定的排序算法。
               
              2.希尔排序
               
              将待排序的序列分成若干个子序列，对每个子序列进行插入排序，使得整个序列基本有序，然后再对整个序列进行插入排序。是插入排序的改进
               
              void ShellSort(int* nums, int numsSize)
              {
                  int group = numsSize;
                  while (group > 1)
                  {
                      //进行分组
                      //加1为了保证最后一次分组为1，组后一次必须要进行正常的插入排序
               	    group = group / 3 + 1;
               	    int i = 0;
                      //每次对分的组进行排序
                      //和插入排序思路相同
               	    for (i = 0; i = 0)
               		    {
               			    if (nums[j] > num)
               			    {
               				    nums[j + group] = nums[j];
               				    j -= group;
               			    }
               			    else
               			    {
               				    break;
               			    }
               		    }
               		    nums[j + group] = num;
               	    }
                  }
              }
               
              group为1时为插入排序，必须要保证最后一次group为1，这样排序才能正确。希尔排序法也称缩小增量法
              希尔排序是对直接插入排序的优化。
              会很快。这样整体而言，可以达到优化的效果。我们实现后可以进行性能测试的对比。
              当group > 1时都是预排序，目的是让数组更接近于有序，让大的数能更快到达后面，小的数可以更快到达前面。当group = 1时，数组已经接近有序的了，这时间使用插入可以让插入排序时间复杂度接近O（N）。从而达到优化效果。希尔排序的时间复杂度大约为O（N^1.3）。
              测试用例：
               
              void sortArray(int* nums, int numsSize)
              {
              	//InsertSort(nums, numsSize);//插入排序
                  ShellSort(nums, numsSize);//希尔排序
              }
              int main()
              {
              	int nums[] = { 3,9,0,-2,1 };
              	int numsSize = sizeof(nums) / sizeof(nums[0]);//计算数组大小
              	sortArray(nums, numsSize);//调用排序算法
              	print(nums, numsSize);//打印排序结果
              	return 0;
              }
               
               
              2.交换排序
               
              1.冒泡排序
               
              void BubbleSort(int* nums, int numsSize)
              {
                  int i = 0;
                  //控制循环次数
                  for (i = 0; i  
              冒泡排序非常容易理解，它的时间复杂度为O(N^2) ，空间复杂度：O(1)且很稳定。
               
              2.快速排序
               
              任取待排序元素序列中的某元素作为标准值，按照该排序码将待排序集合分成两段，左边中所有元素均小于该值，右边中所有元素均大于该值，然后左右两边重复该过程，直到所有元素都排列在相应位置上为止。
               
              1.hoare版
               
              void PartSort1(int* nums, int left, int right)
              {
                  //当区间不存在或者区间只有一个数时结束递归
                  if (left >= right)
                  {
               	    return ;
                  }
                  int key = left;
                  int begin = left;
                  int end = right;
                  while (begin