常见排序算法（算法思想以及C++代码实现）-创新互联
- 常见排序算法
- 选择排序
- 算法思想
- 代码实现
- 复杂度分析
- 冒泡排序
- 算法思想
- 代码实现
- 复杂度分析
- 插入排序
- 算法思想
- 代码实现
- 复杂度分析
- 归并排序
- 算法思想
- 代码实现
- 复杂度说明
- 快速排序
- 算法思想
- 代码实现
- 复杂度说明
- 堆排序
- 算法思想
- 代码实现
- 复杂度说明
- 写在最后
选择排序 算法思想本文旨在讲解常见排序算法的思想，并会附上完整版C++代码实现，为了更好的说明问题，本文章中，所有排序均以升序为例，期待您的一键三连！！！
代码实现选择排序其实是一个很容易理解的算法，它的要求是，我每遍历一次数组，就从数组中选出一个最小的数字放在数组的未排序部分的数字的最前面；下一次遍历时，只遍历未排序部分，同样选择出最小的数字放在未排序部分的最前面，周而复始即可。
#includeusing namespace std;
void printArr(int arr[], int len) //实时打印数组，便于更好地了解排序的具体过程
{for (int i = 0; i< len; ++i)
cout<< arr[i]<< "\t";
cout<< endl;
}
void swap(int arr[], int i, int j) //交换函数
{if (i == j)
return;
arr[i] = arr[i] ^ arr[j];
arr[j] = arr[i] ^ arr[j];
arr[i] = arr[i] ^ arr[j];
}
void selectionSort(int arr[], int len) //需要传入的参数是数组本身以及数组长度len
{for (int i = 0; i< len - 1; ++i)
//只需要到len-2的原因是，前len-1个都有序了，那最后一个一定是大的（因为我每一次循环选的都是最小的）
{for (int j = i + 1; j< len; ++j)
{ if (arr[j]< arr[i])
swap(arr, i, j);
}
cout<< "第"<< i + 1<< "次排序后的结果为:";
printArr(arr, len);
}
}
int main()
{int arr[10] = {10,9,8,7,6,1,3,4,2,5 };
selectionSort(arr, 10);
return 0;
} 
冒泡排序 算法思想一个双层嵌套循环，
- i=0时，内层循环（n-1）次
- i=1时，内层循环（n-2）次
…
i=len-2时，内层循环1次等差数列求和，所以时间复杂度是 O ( N 2 ) O(N^2) O(N2)。
而关于空间复杂度，可以发现几乎没有引入额外的变量来存储中间过程，只有i、j以及swap中的temp，且每一次用完后都是销毁了，所以空间复杂度是 O ( 1 ) O(1) O(1)
代码实现在每一轮的循环中，我的做法都是相邻的两个数比较大小，如果左边的数比右边的数大，那么我就将这两个数交换位置，这样，每一轮循环过后，都会发现，未排序部分的大数都被放到了数组的末尾。而这也是冒泡的基本思想。
#includeusing namespace std;
void printArr(int arr[], int len) //实时打印数组，便于更好地了解排序的具体过程
{for (int i = 0; i< len; ++i)
cout<< arr[i]<< "\t";
cout<< endl;
}
void swap(int arr[], int i, int j) //交换函数
{if (i == j)
return;
arr[i] = arr[i] ^ arr[j];
arr[j] = arr[i] ^ arr[j];
arr[i] = arr[i] ^ arr[j];
}
void bubbleSort(int arr[], int len)
{for (int i = 0; i< len - 1; ++i)
//也是需要len-1轮循环就行了，因为每一轮循环都有一个大的数放到了后面，那么len-1个大数放到了后面，剩下的那个就一定是小数了
{for (int j = 0; j< len - 1 - i; ++j) //len-1-i后面的大数位置都已经正确了，不需要再比较了
{ if (arr[j] >arr[j + 1])
swap(arr, j, j + 1);
}
cout<< "第"<< i + 1<< "次循环后的结果为:";
printArr(arr, len);
}
}
int main()
{int arr[10] = {10,9,8,7,6,5,4,3,2,1 };
bubbleSort(arr, 10);
return 0;
} 
插入排序 算法思想这个的时间复杂度以及空间复杂度和选择排序的完全一样，且分析方法完全一致，不再详述。
代码实现假设[0,i-1]的元素都已经按照从小到大的顺序排好了，那么对于第i个元素，我先将它与第i-1个元素比较大小，如果i大，那么i的位置直接正确（至少在没有研究后面的元素的时候，这么认为是完全没有问题的），然后i后面的元素就行了。如果i比i-1的元素小，那么就在将i和i-2比较，如果还小，接着和i-3比较，周而复始，直到找到i应该在的位置x，把x后面的元素依次后移，把i元素放到位置x即可。
#includeusing namespace std;
void printArr(int arr[], int len) //实时打印数组，便于更好地了解排序的具体过程
{for (int i = 0; i< len; ++i)
cout<< arr[i]<< "\t";
cout<< endl;
}
void swap(int arr[], int i, int j) //交换函数
{if (i == j)
return;
arr[i] = arr[i] ^ arr[j];
arr[j] = arr[i] ^ arr[j];
arr[i] = arr[i] ^ arr[j];
}
void insertSort(int arr[], int len)
{for (int i = 1; i< len; ++i)
//从i=1开始，因为我认为arr[0]初始的时候就是默认有序的
{for (int j = i - 1; j >= 0; --j)
{ if (arr[j] >arr[j + 1])
//注意这里的判断条件不要写成arr[j]>arr[i]
//简单解释就是如果这样写，arr[i]只要与arr[i-1]交换了，循环不会再进行了，因为新的arr[i]是一定大于arr[i-2]的，因为之前已经有序了
swap(arr, j + 1, j);
else
break; //当前这个数都没有i大了，后面的就更不用看了呗，所以可以直接break掉
}
cout<< "第"<< i<< "次循环后的结果为:";
printArr(arr, len);
}
}
int main()
{int arr[10] = {10,9,8,7,6,5,4,3,2,1 };
insertSort(arr, 10);
return 0;
} 
归并排序 算法思想时间复杂度 O ( N 2 ) O(N^2) O(N2),空间复杂度 O ( 1 ) O(1) O(1),不必详述原因，因为确实很好分析。
代码实现归并排序主要运用了分治思想，对于一个大的待排序的数组，可以将其分成两个小数组，对两个小数组分别进行排序，然后对两个有序部分合并，从而导致大数组有序。而对于每一个小数组，也是将其划分成更小的数组进行相同的操作。这里其实也体现了一个递归的思想。
#includeusing namespace std;
void process(int arr[], int left, int mid, int right)
{int* help = new int[right - left + 1]; //额外申请的数组，便于合并操作
int pl = left; //左半部分数组的起始下标
int pr = mid + 1; //右半部分数组的其实下标】
int i = 0; //help数组的起始下标
while (pl<= mid && pr<= right)
help[i++] = arr[pl]< arr[pr] ? arr[pl++] : arr[pr++];
while (pl<= mid)
help[i++] = arr[pl++];
while (pr<= right)
help[i++] = arr[pr++];
for (i = 0; i< right - left + 1; ++i) //别忘了拷贝回去
arr[left + i] = help[i];
}
void merge(int arr[], int left, int right)
{if (left >= right) //递归终止条件是一定要写明白的
return;
int mid = left + ((right - left) >>1);
merge(arr, left, mid);
merge(arr, mid + 1, right);
process(arr, left, mid, right);
}
int main()
{int arr[10] = {10, 9,8,7,6,5,4,3,2,1 };
merge(arr, 0, 9);
for (int i = 0; i< 10; ++i)
cout<< arr[i]<< "\t";
return 0;
} 
快速排序 算法思想时间复杂度 O ( N l o g N ) O(NlogN) O(NlogN),空间复杂度 O ( N ) O(N) O(N)
代码实现其实这个算法的引入是来自于荷兰国旗问题的，想了解该问题的小伙伴可以自行百度一下。它的主要思想是从数组中随机选取一个数作为基准值key,然后将数组中比key小的数字都放在数组的前半段（不要求有序），将值等于key的数字都放在数组的中间，将值比key大的元素都放在数组的末尾；然后对于数组的前半段和后半段都做同样的递归处理，直至所有元素有序。
#include#includeusing namespace std;
void swap(int arr[], int i, int j) //交换函数
{if (i == j)
return;
arr[i] = arr[i] ^ arr[j];
arr[j] = arr[i] ^ arr[j];
arr[i] = arr[i] ^ arr[j];
}
int* partition(int arr[], int left, int right)
{int less = left - 1; //<区域的右边界
int more = right; //>区域的左边界
while (left< more)
{if (arr[left]< arr[right])
swap(arr, left++, ++less);
else if (arr[left] >arr[right])
swap(arr, left, --more);
else
left++;
}
swap(arr, more++, right);
return new int[2] {less, more};
}
void quickSort(int arr[], int left, int right)
{if (left >= right)
return;
swap(arr, right, (left + (rand() % (right - left + 1))));
int* p = partition(arr, left, right);
quickSort(arr, left, p[0]);
quickSort(arr, p[1], right);
}
int main()
{int arr[10] = {10, 9,8,7,6,5,4,3,2,1 };
quickSort(arr, 0, 9);
for (int i = 0; i< 10; ++i)
cout<< arr[i]<< "\t";
return 0;
} 
堆排序 算法思想时间复杂度 O ( n l o g n ) O(nlogn) O(nlogn),这个是数学家证明的，证明起来是比较复杂的，之所以复杂，主要是在于它的那个key是随机选择的,不必深究。空间复杂度是 O ( l o g n ) O(logn) O(logn),现在只需要知其然就行，不需要知其所以然。
代码实现了解这个算法需要读者需要有完全二叉树、大根堆、小根堆的预备知识（可自行查阅资料），本身也是很简单的。以升序为例，我们主要采用大根堆的形式，当将给定的数组化成大根堆的形式后，将根节点与堆中最后一个元素互换位置，然后heapSize减1，表示将大的元素已经从堆中去除了，并且由于我们已经将其和最后一个元素互换位置了，那么这个元素实际上也就被放到了数组的最后一个位置，而对于剩下的元素，我们重新进行堆化操作。周而复始,知道heapSize被减至0即可。
#include#includeusing namespace std;
void swap(int arr[], int i, int j) //交换函数
{if (i == j)
return;
arr[i] = arr[i] ^ arr[j];
arr[j] = arr[i] ^ arr[j];
arr[i] = arr[i] ^ arr[j];
}
void heapInsert(int arr[], int pos)
//这个函数的作用是给定一个元素（以下标形式给出，成功将其放到堆中合适位置以保证形成大根堆）
//某个数在index位置，他能否向上移动
{while (arr[pos] >arr[(pos - 1) / 2])
{swap(arr, pos, (pos - 1) / 2);
pos = (pos - 1) / 2;
}
}
void heapify(int arr[], int index, int heapSize)
//某个数在index位置，他能否向下移动
{if (heapSize == 0)
return;
int left = 2 * index + 1;
while (left< heapSize) //有孩子的情况下，才有向下移动的可能
{int largest = ((left + 1< heapSize) && arr[left + 1] >arr[left]) ? left + 1 : left;
largest = arr[index] >arr[largest] ? index : largest;
if (largest == index)
break;
swap(arr, index, largest);
index = largest;
left = 2 * index + 1;
}
}
void heapSort(int arr[], int len)
{if (len< 2)
return;
for (int i = 0; i< len; ++i)
heapInsert(arr, i);
int heapSize = len;
while (heapSize >0)
{swap(arr, 0, heapSize - 1);
heapSize--;
heapify(arr, 0, heapSize); //重新对新的堆头进行堆化操作
}
}
int main()
{int arr[10] = {10, 9,8,7,6,5,4,3,2,1 };
heapSort(arr, 10);
for (int i = 0; i< 10; ++i)
cout<< arr[i]<< "\t";
return 0;
} 
写在最后时间复杂度 O ( n l o g n ) O(nlogn) O(nlogn),空间复杂度 O ( l o g n ) O(logn) O(logn)
后面文章还会持续更新，您的支持是我创作的动力，期待您的一键三连！！！
你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧
文章标题：常见排序算法（算法思想以及C++代码实现）-创新互联
链接URL：http://myzitong.com/article/ccoepj.html