C++：排序算法

目录

一、插入排序

1.直接插入排序

2.希尔排序

二、交换排序

1.冒泡排序

2.快速排序 

三、选择排序

1.简单选择排序

2.堆排序

四、归并排序

1.二路归并排序的递归实现

2.二路归并排序的非递归实现

---

 

一、插入排序

1.直接插入排序

        直接插入排序的基本思想是：依次将待排序序列中的每一个记录插入到已排好序的序列中，直到全部记录都排好序。（记录就是排序问题中的数据元素）

        平均时间复杂度为O(n^2)。

        直接插入排序是一种稳定的排序方法。

        待排序记录基本有序时，直接插入排序的效率很高。

vector<int> nums = { 5,0,1,2,7,3,9,6,4,8 };        //待排序序列for (int i = 1; i < nums.size(); i++)              //将第1个记录当作有序序列，从第2个记录开始执行插入操作             
{int temp = nums[i];                            //暂存当前记录，当前记录之前都是有序的int j;for (j = i - 1; j >= 0 && temp < nums[j]; j--) //从后往前遍历有序序列{nums[j + 1] = nums[j];                     //记录后移1位}nums[j + 1] = temp;                            //插入记录
}

2.希尔排序

        希尔排序（Shell sort）是对直接插入排序的一种改进，当待排序列基本有序以及待排序记录个数较少时，直接插入排序的效率都很高，于是将序列分割以及让序列向基本有序发展。

        希尔排序的基本思想是：先将整个待排序序列分割成若干个子序列，在子序列内分别进行直接插入排序。

        时间复杂度为O(nlog2n)~O(n^2)。（前一个2为底数）

        由于在希尔排序过程中记录是跳跃移动的，因此希尔排序是不稳定的。

vector<int> nums = { 5,0,1,2,7,3,9,6,4,8 };           //待排序序列for (int d = nums.size() / 2; d >= 1; d = d / 2)      //以增量d来分割子序列并进行直接插入排序//最后一趟排序时d=1，即不分割，此时序列已基本有序
{for (int i = d; i < nums.size(); i++)             //从这里开始类似于直接插入排序{int temp = nums[i];                           //暂存待排序记录int j;for (j = i - d; j >= 0 && temp < nums[j]; j -= d){nums[j + d] = nums[j];                    //记录后移d位}nums[j + d] = temp;                           //插入记录}
}

二、交换排序

1.冒泡排序

        冒泡排序（bubble sort）的基本思想是：两两比较相邻记录，如果反序则交换，直到没有反序的记录为止。每趟排序都将使得序列的右边多一个有序记录。

        平均时间复杂度为O(n^2)。

        冒泡排序是稳定的排序方法。

vector<int> nums = { 5,0,1,2,7,3,9,6,4,8 };             //待排序序列for (int i = 0; i < nums.size() - 1; i++)               //只需排n-1趟
{for (int j = 0; j < nums.size() - 1 - i; j++)       //遍历无序序列{if (nums[j] > nums[j + 1])                      //若反序，则交换{int temp = nums[j];nums[j] = nums[j + 1];nums[j + 1] = temp;}}
}

2.快速排序 

        快速排序（quick sort）是对冒泡排序的一种改进，减少了总的比较次数和移动次数。

        快速排序的基本思想是：选定一个轴值（pivot，即比较的基准），将待排序记录划分成两部分，左侧记录均小于或等于轴值，右侧记录均大于或等于轴值，然后分别对这两部分重复上述过程，直到整个序列有序。可以直接选择第一个记录作为轴值。

        平均时间复杂度是O(nlog2n)。（2为底数）

        快速排序是不稳定的排序。

        快速排序的平均时间性能是迄今为止所有内排序算法中最好的，因此得到广泛应用。

vector<int> nums = { 5,0,1,2,7,3,9,6,4,8 };   //待排序序列/*作一次划分，参数是被划分的序列的左右下标*/
int partition(int left, int right)               
{int i = left, j = right;while (i < j)                             //多次左、右侧扫描{while (i < j && nums[i] <= nums[j])   //j指向比i所指的数还小的数（右侧扫描）{j--;}if (i < j)                            //若i还在j左边，交换两数，即把较大者往右放{int temp = nums[i];nums[i] = nums[j];nums[j] = temp;i++;}while (i < j && nums[i] <= nums[j])   //i指向比j所指的数还大的数（左侧扫描）{i++;}if (i < j)                            //若i还在j左边，交换两数，即把较大者往右放{int temp = nums[i];nums[i] = nums[j];nums[j] = temp;j--;}}return i;                                 //此时i=j，已划分完毕（i的左边全小于它，右边全大于它）
}/*快速排序函数，递归执行，参数是待排序序列的左右下标*/
void quick_sort(int left, int right)            
{if (left >= right)                        //子序列只剩一个记录，无需再排{return;}else{int pivot = partition(left, right);   //作一次划分quick_sort(left, pivot - 1);          //对左侧子序列进行快速排序quick_sort(pivot + 1, right);         //对右侧子序列进行快速排序}
}quick_sort(0, nums.size() - 1);               //调用函数对序列nums进行快速排序

三、选择排序

1.简单选择排序

        简单选择排序（simple select sort）的基本思想是：在无序序列中找出最小的记录，然后放在无序序列的最左端，重复该过程，直到序列全部有序。

        平均时间复杂度为O(n^2)。

        简单选择排序是不稳定的排序。

vector<int> nums = { 5,0,1,2,7,3,9,6,4,8 };    //待排序序列for (int i = 0; i < nums.size()-1; i++)        //只需选择n-1次           
{int index = i;                             //index存最小数的下标，初始化为最左侧下标for (int j = i + 1; j < nums.size(); j++)  //遍历无序序列{if (nums[j] < nums[index])             //若遍历到的数更小，index存其下标{index = j;}}if (index != i)                            //若最小数不在最左侧，则移到最左侧{int temp = nums[i];nums[i] = nums[index];nums[index] = temp;}
}

2.堆排序

        堆排序是简单选择排序的改进，改进的着眼点是在选出最小记录的同时，也找出较小记录，减少了记录的比较次数。

        堆排序的基本思想是：首先将待排序序列调整成一个堆，将堆顶移走作为最大者，并将剩余记录再调整成堆，又将堆顶移走作为次大者，依此类推，直到得到整个有序序列。

        平均时间复杂度为O(nlog2n)。（2为底数）

        堆排序是不稳定的排序。

        堆排序对待排序序列的初始状态并不敏感，相对于快速排序，这是堆排序最大的优点。

vector<int> nums = { 5,0,1,2,7,3,9,6,4,8 };        //待排序序列/*堆调整，参数为待排序列，被调整节点和最后一个节点的下标（用于防止数组越界）*/
void sift(vector<int>& nums, int sorted_num, int last)  
{int parent(sorted_num);                        //父节点int child(2 * sorted_num + 1);                 //左孩子节点while (child <= last)                          //尚未越界{//将child指向孩子中的较大者，child<last意味着有右孩子if (child < last && nums[child] < nums[child + 1]) {child++;                               //child+1即指向右孩子}if (nums[parent] > nums[child])            //父节点更大，满足堆条件，结束{break;}else                                       //否则，交换父子节点并更新父子节点{int temp = nums[parent];nums[parent] = nums[child];nums[child] = temp;parent = child;child = 2 * parent + 1;}}
}/*堆排序函数，参数是待排序列*/
void heap_sort(vector<int>& nums)                       
{//初始化堆，最后一个分支节点的下标为nums.size()/2-1  for (int i = nums.size() / 2 - 1; i >= 0; i--)      {sift(nums, i, nums.size() - 1);}//将堆顶和最后一个节点交换，再重建堆，每交换一次堆减少一个元素（j--）for (int j = nums.size() - 1; j > 0; j--)           {int temp = nums[0];nums[0] = nums[j];nums[j] = temp;sift(nums, 0, j - 1);}
}heap_sort(nums);                                  //对序列nums进行堆排序

四、归并排序

        归并排序（merge sort）的基本思想是：将若干个有序序列逐步归并，最终归并为一个有序序列。

        常用的是二路归并排序，其基本思想是：将待排序列划分为两个长度相等的子序列，分别对这两个子序列进行排序，再将这两个有序子序列合并成一个有序序列。 

        平均时间复杂度为O(nlog2n)。（2为底数）

        二路归并排序是一种稳定的排序方法。

1.二路归并排序的递归实现

vector<int> nums = { 5,0,1,2,7,3,9,6,4,8 };     //待排序序列/*用于合并两个相邻子序列[left_1, right_1]和[right_1 + 1, right_2], 得到[left_1, right_2]*/
void merge(int left_1, int right_1, int right_2)  
{int* temp = new int[nums.size()];           //申请一个合并辅助空间int i = left_1, j = right_1 + 1, k = left_1;while (i <= right_1 && j <= right_2)        //当两个序列都还有待排元素时{if (nums[i] <= nums[j])                 //取较小者放入辅助空间{temp[k++] = nums[i++];}else{temp[k++] = nums[j++];}}while (i <= right_1)                        //若第二个序列无待排元素{temp[k++] = nums[i++];  //将第一个序列剩余元素全部放入辅助空间}while (j <= right_2)                        //若第一个序列无待排元素{temp[k++] = nums[j++];  //将第二个序列剩余元素全部放入辅助空间}for (i = left_1; i <= right_2; i++)         //将合并结果放回原序列{nums[i] = temp[i];}delete[] temp;                              //释放合并辅助空间
}/*二路归并排序的递归算法，对[left,right]进行排序*/
void merge_sort(int left, int right)
{if (left == right)                           //只有1个记录，递归结束{return;}else{int mid = (left + right) / 2;            //分割为两个子序列merge_sort(left, mid);                   //对前半部分归并排序merge_sort(mid + 1, right);              //对后半部分归并排序merge(left, mid, right);                 //将两个子序列归并}
}merge_sort(0, nums.size() - 1);                  //对序列nums归并排序

2.二路归并排序的非递归实现

         二路归并排序的递归实现是一种自顶向下的方法，形式简洁但效率相对较差。二路归并排序的非递归实现是一种自底向上的方法，算法效率较高，但算法较复杂。

vector<int> nums = { 5,0,1,2,7,3,9,6,4,8 };     //待排序序列/*用于合并两个相邻子序列[left_1, right_1]和[right_1 + 1, right_2], 得到[left_1, right_2]*/
void merge(int left_1, int right_1, int right_2)
{int* temp = new int[nums.size()];           //申请一个合并辅助空间int i = left_1, j = right_1 + 1, k = left_1;while (i <= right_1 && j <= right_2)        //当两个序列都还有待排元素时{if (nums[i] <= nums[j])                 //取较小者放入辅助空间{temp[k++] = nums[i++];}else{temp[k++] = nums[j++];}}while (i <= right_1)                        //若第二个序列无待排元素{temp[k++] = nums[i++];  //将第一个序列剩余元素全部放入辅助空间}while (j <= right_2)                        //若第一个序列无待排元素{temp[k++] = nums[j++];  //将第二个序列剩余元素全部放入辅助空间}for (i = left_1; i <= right_2; i++)         //将合并结果放回原序列{nums[i] = temp[i];}delete[] temp;                              //释放合并辅助空间
}/*执行一趟归并排序*/
void merge_pass(int h)
{int i(0);while (i + 2 * h <= nums.size())            //有两个长度为h的子序列{merge(i, i + h - 1, i + 2 * h - 1);     //合并前两个子序列i = i + 2 * h;                          //准备合并下两个子序列}if (i + h < nums.size())  //有两个长度分别等于h和小于h的子序列，合并它们{merge(i, i + h - 1, nums.size() - 1);}
}/*二路归并排序的非递归算法*/
void merge_sort()
{int h(1);                                    //初始子序列长度为1while (h < nums.size()){merge_pass(h);h = 2 * h;}
}merge_sort();                                    //对序列nums归并排序