排序算法介绍及实现：选择；冒泡；归并；快排等
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了排序算法介绍及实现：选择；冒泡；归并；快排等，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含5830字，纯文字阅读大概需要9分钟。
内容图文
排序算法
记录一下最近学习的各种排序算法。
目录：
选择排序
选择排序是最简单且容易想到的排序方法。它把输入值(以下均以列表为例)分为两个部分：已排序 和 未排序部分。
先看一组伪代码：
for (i = 0; i < numbersSize - 1; ++i){
//找到未排序部分中最小值的索引值
indexSmallest = i
for (j = i + 1; i < numbersSize; ++j){
if (numbers[j] < numbers[indexSmallest]){
indexSmallest = j
}
}
//找到余下值中最小的索引值，与第i个值交换。若没找到则不变
temp = numbers[i]
numbers[i] = numbers[indexSmallest
numbers[indexSmallest] = temp
}
思路：
- 两个循环把列表分为已排序和未排序两部分，用 i，j 去表示
- 该算法找到未排序中最小值的索引值
- 把索引值上的元素与i元素交换
- i，j 更新，表示出新的已排序未排序部分
- 直到 i 小于长度 -1，遍历停止。因为不再需要单独遍历最后一个元素。
时间复杂度：O(n^2)
该算法或将运行多次比较。当列表长度为N时，外层循环将执行 N - 1 次。在这些外循环中，内层循环每次将执行平均 N / 2 次。所以，(N - 1) x (N / 2) = O(N ^ 2)。此算法也是众多排序算法中最慢的算法之一。
插入排序
同样的，插入排序也将列表分为已排序和未排序部分。不同的是，此算法每次只在未排序部分中提取第一个元素，然后把它放到已排序部分中合适的位置。
先看一组伪代码：
for (i = 1; i < numbersSize; ++i){
j = 1
//把第i个元素放入到已排序的部分（第二个元素开始。默认第一个元素是以排好部分）
//i已经到第一个位置时，或当第i个元素放入到正确位置时，停止while循环。
while (j > 0 && number[j] < numbers[j - 1]){
//把第i位的数和前一位交换 [j]和[j-1]
temp = numbers[j]
numbers[j] = numbers[j - 1]
numbers[j - 1] = temp
--j
}
}
这次要外层要循环到长度而不是长度 - 1，因为我们也要把最后一个元素放到正确的位置上。
思路：
- 将第i个元素作为第一个未排序部分的起点。因为我们无需排序索引0，所以 i 为1。
- 第j个元素一直标记为我们要插入的元素。如果该元素比前一个元素小，则互换。
- 当第i个元素放置到正确的位置后，i + 1。循环下一位元素并放置到正确位置。
- 如果要插入的元素比前面所有元素值都要小，则该元素依次循环到列表第一位，随之 j = 0打破循环。
时间复杂度：O(n^2)
该算法实际上效率与选择排序同理，复杂度均为O(n^2)。因为外层循环执行N - 1次，而内层循环同样每次平均执行N/2 次。(N - 1) x (N / 2) = O(N ^ 2)。
冒泡排序
该算法不再将列表分为两个部分，每次只比较两个相邻的元素然后调整位置。
先看一组伪代码：
for (i = 0; i < numbersSize - 1; ++i){
for (j = 0; j < numbersSize - i - 1; ++j){
if (numbers[j] > numbers[j+1]){
temp = numbers[j]
numbers[j] = numbers[j + 1]
numbers[j + 1] = temp
}
}
}
思路：
- 该算法从第一个元素开始，依次和后面的元素比较。若后一位元素小于前一位元素则互换。
- 内层循环结束后，该列表中最大的元素已确定到最后一位。然后重新遍历列表。
- 当 i = 长度 - 1 时，结束遍历，此时列表已排好序。
- 与前两种算法不同，该算法依次优先排好后面的顺序，而不是前面。
时间复杂度：O(n^2)
因为嵌套循环，该算法的时间复杂度仍为O(n^2)。
归并排序
该算法用到递归解决，分为两个部分。第一个部分为递归函数，该函数每次平均把列表分为两个部分，分别去递归。第二个部分为一个排序函数，用来排递归回来的列表。
来看两组伪代码：
//递归函数内容：
merge(numbers, start, end){
mid = (start + end)/2
merge(numbers, start, mid)//递归mid左边
merge(numbers, mid+1, end)//递归mid右边
//把start到mid和mid到end的元素排列好
mergeHelper(numbers, start, mid, end)
}
//排序函数
mergeHelper(numbers, start, mid, end){
mergeSize = end - start + 1 //要归并的大小
mergePos = 0 //归并元素的位置
leftPos = 0 //元素左边部分的位置
rightPos = 0 //元素右边部分的位置
mergedNumbers = new int [mergedSize]
//放置已归并好的元素
leftPos = start //初始化左边位置
rightPos = mid + 1 //初始化右边位置
//从左到右添加最小的元素到mergedNumbers
while (leftPos <= mid && rightPos <= end){
if (numbers[leftPos])<= numbers[rightPos]{
mergedNumbers[mergePos] = numbers[leftPos]
++leftPos
}
else{
mergedNumbers[mergePos] = numbers[rightPos]
++rightPos
}
++mergePos
}
//当左边没添加完，右边已经添加完时，把左边剩下的加到mergedNumbers
while(leftPos <= mid){
mergedNumbers[mergePos] = numbers[leftPos]
++leftPos
++mergePos
}
//右边同理
while (rightPos <= end) {
mergedNumbers[mergePos] = numbers[rightPos]
++rightPos
++mergePos
}
//最后，把排好序的列表放回到原列表中
for (mergePos = 0; mergePos < mergedSize; ++mergePos) {
numbers[start + mergePos] = mergedNumbers[mergePos]
}
}
思路已写在注释中。
时间复杂度：O(N log N)
该算法重复平分列表直到每个列表的元素数为1。此做法会构成log N层列表。每层列表中运行N次比较运算，所以一共有 N * log N次运算，而该算法成为最有效率的排序算法之一。
空间复杂度：O(N)
快速排序
与归并排序类似，快排也用到了递归去解决问题。该算法随意取一个元素为基准数pivot。把所有比它小的元素放在它的前面，比它大的元素放在后面。在以pivot为中心把列表分别递归，直到个数为1。
再来看两组伪代码：
quickSort(numbers, lowIndex, highIndex){
//基本情况：如果该部分长度是1或0，则该部分已经排好序
if (lowIndex >= highIndex){
return
}
//lowEndIndex为小于的部分的最后一个元素
lowEndIndex = partition(numbers, lowIndex, highIndex)
//递归小于的部分和大于的部分
quickSort(numbers, lowIndex, lowEndIndex)
quickSort(numbers, lowEndIndex + 1, highIndex)
}
partition(numbers, lowIndex, highIndex){
//随意挑选一个pivot，以中位数为例
midpoint = lowIndex + (highIndex - lowIndex)/2
pivot = numbers[midpoint]
done = false
while(!done){
//当numbers[lowIndex] < pivot时，增加lowIndex
while (numbers[lowIndex] < pivot){
lowIndex += 1
}
//当numbers[highIndex] > pivot时，增加highIndex
while (numbers[highIndex] > pivot){
highIndex -= 1
}
if (lowIndex >= highIndex){
done = true
}
else{
//互换numbers[lowIndex]和numbers[highIndex]
temp = numbers[lowIndex]
numbers[lowIndex] = numbers[highIndex]
numbers[highIndex] = temp
//更新lowIndex, highIndex
lowIndex += 1
highIndex -= 1
}
}
return highIndex
}
思路已写在注释中。
时间复杂度O(N Log N) -> O(n^2)
通常来说，该算法的时间复杂的为O(N Log N)。特殊情况下，当每一层的pivot都选择了最大或是最小的元素，则此情况下的时间复杂度为O(n^2)。但是由于这种情况的发生概率小之又小，该算法是最有效率的排序算法之一。
后面会更新更多的排序算法，此博客仅用于自我学习的记录，如有不当请指正。
内容总结
以上是互联网集市为您收集整理的排序算法介绍及实现：选择；冒泡；归并；快排等全部内容，希望文章能够帮你解决排序算法介绍及实现：选择；冒泡；归并；快排等所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。