C++算法初级5——排序1

本文介绍排序的几种方法，默认均为从小到大排序，内容来源参考boyuai

选择排序

基本思想：

1. 将1-n位的元素依次归位
2. 当归位第i个元素时，需要选出第i位元素~第n位元素的最小值，和第i位元素互换位置，此时此时，1到i的元素分别为第1小到第i小的元素。
3. 当第n个元素归位完毕以后，整个序列的排序过程结束。

代码

void selectSort(int a[], int n)
{for (int i=0;i<n;i++){int min = i;for (int j=i+1;j<n;j++){if (a[j] < a[min]){min = j;}}if (min != i){int temp = a[i];a[i] = a[min];a[min] = temp;}}// 输出for (int i=0;i<n;i++){cout << a[i] << " ";}
}

复杂度O(n2)O(n^2)O(n2)

冒泡排序

基本思想：

1. 冒泡排序和选择排序一样，都是将原问题转换为长度减一的子问题的过程。
2. 冒泡排序分为n-1个阶段，每个阶段通过“冒泡”的过程，将未排序序列中的最大值移动到最后一位。
3. 冒泡的过程，具体是通过一段连续交换过程使得最大元素被“传送”到最后一位。
4. 冒泡排序的思路：

冒泡排序分为n-1个阶段。

在第1个阶段，通过“冒泡”，我们将前n个元素的最大值移动到序列的最后一位。此时只剩前n-1个元素未排序。

在第i个阶段，此时序列前n-i+1个元素未排序。通过“冒泡”，我们将前n-i+1个元素中的最大值移动到最后一位。此时只剩前n-i个元素未排好序。

对一段序列从左到右连续做交换操作的代码：

if (a[i] > a[i + 1]) swap(a[i], a[i + 1]);

代码

//冒泡排序
void bubbleSort(int a[],int n)
{for(int i=0;i<n-1;i++) // 一共n-1个阶段，在第i个阶段，未排序序列长度从0到n-i-1。{for(int j=0;j<n-i-1;j++) //循环的角标只到n-i-2，因为会考虑j+1即n-i-1{if(a[j]>a[j+1]){swap(a[j],a[j+1]);}}}//输出  for(int i=0;i<n;i++){cout<<a[i]<<" ";}
}

复杂度O(n2)O(n^2)O(n2)

插入排序

插入排序的基本思想就是不断扩展有序序列的长度。

具体方式是对于一个有序序列，如果想在其中新加入一个元素，就应通过插入操作找出正确的插入位置，并且将插入位置空出来，然后插入新元素。

插入操作的基本思想就是从后向前不断“试探”分界线的位置。

一个合法的分界线，分界线前的元素需满足小于等于新元素大小，分界线后元素需满足大于新元素大小。所以寻找分界线的过程，就是不断把当前在分界线前，但本应该在分界线后的元素向后移动。

插入操作的算法描述：

假设序列1~(i-1)已经有序, 从i到1枚举分界线的下标j;

如果分界线前面的元素a[j-1]大于x，说明a[j-1]应该在分界线后面。所以将a[j-1]移动到a[j]，分界线前移变成j-1。

如果分界线前面没有元素（j=1），就将x放在数组第1位。否则如果碰到一个j-1号元素小于等于x，说明分界线位置正确，就将x插到j位。

代码：

// 插入排序
void insertSort(int a[],int n)
{for(int i=1;i<n;i++) // 从第二个元素开始，第一个元素认为是有序的{int temp = a[i]; // 保存当前元素int j = i-1; // 从当前元素的前一个元素开始while(j>=0 && a[j]>temp) // 从后往前遍历，直到找到比当前元素小的元素{a[j+1] = a[j]; // 后移j--;}a[j+1] = temp; // 插入}// 输出for(int i=0;i<n;i++){cout<<a[i]<<" ";}
}

复杂度O(n2)O(n^2)O(n2)