冒泡（bubblesort）、选择排序、插入排序、快速排序
2024-08-29 09:41:26
冒泡排序（bubblesort）
特点：通过换位置的方式，一直向上冒泡
package main
import "fmt"
func bubbleSortAsc(arrayA []int){
for i:=0; i < len(arrayA); i++ {
for j:=0; j < len(arrayA)-1-i; j++ {
if arrayA[j] > arrayA[j+1]{
arrayA[j], arrayA[j+1] = arrayA[j+1], arrayA[j]
}
}
}
fmt.Println(arrayA)
}
func bubbleSortDesc(arrayA []int){
for i:=0; i < len(arrayA); i++{
for j:=0; j < len(arrayA)-1-i; j++{
if arrayA[j] < arrayA[j+1]{
arrayA[j], arrayA[j+1] = arrayA[j+1], arrayA[j]
}
}
}
fmt.Println(arrayA)
}
func main(){
var arrayA []int = []int{1,3,5,2,9,10,6,4,8,7}
bubbleSortAsc(arrayA)
bubbleSortDesc(arrayA)
}
快速排序（quicksort）
基本思想：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分都要小，然后再按此方法对两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列
复杂度：快速排序是最不稳定的算法，最坏的时间复杂度是O(n2)，最好的时间复杂度是 nlogn，空间复杂度是O(logn)
demo：
package main
import "fmt"
func QuickSort(aSlice []int, start, end int) {
if start >= end {
return
}
var low, high = start, end //low 为由左向右的游标， high为由右向左的游标
var mid = aSlice[start] // 基数
for low < high {
//如果 low 与 high 未重合，high指向的元素不比基准元素小，则high往左移动
for low < high && aSlice[high] >= mid {
high--
}
aSlice[low] = aSlice[high]
//如果 low 与 high 未重合，low指向的元素不比基准元素小，则low往右移动
for low < high && aSlice[low] < mid {
low ++
}
aSlice[high] = aSlice[low]
}
//将基准元素放到该位置
aSlice[low] = mid
//对基准元素左边的子序列进行快速排序
QuickSort(aSlice, start, low - 1)
//对基准元素右边的子序列进行快速排序
QuickSort(aSlice, low + 1, end)
}
func main (){
var aSlice = []int{2,5,4,6,9,8,10,1,3,7}
QuickSort(aSlice, 0, len(aSlice) - 1)
fmt.Println(aSlice)
}
python 版本：
# coding: utf8 def quick_sort(alist, start, end):
if start >= end:
return # low为由左向右的游标， high为由右向左的游标
low = start
high = end
mid = alist[start] # 基数 while low < high:
# 如果 low 与 high 未重合，high指向的元素不比基准元素小，则high往左移动
while low < high and alist[high] >= mid:
high -= 1
alist[low] = alist[high] # 如果 low 与 high 未重合，low指向的元素不比基准元素小，则low往右移动
while low < high and alist[low] < mid:
low += 1
alist[high] = alist[low] # 将基准元素放到该位置
alist[low] = mid
# 对基准元素左边的子序列进行快速排序
quick_sort(alist, start, low - 1)
# 对基准元素右边的子序列进行快速排序
quick_sort(alist, low + 1, end) if __name__ == '__main__':
# alist = [2, 5, 4, 6, 9, 7, 8, 1, 10, 3]
alist = [6, 5, 8, 2, 9, 4, 10, 1, 3, 7]
quick_sort(alist, 0, len(alist) - 1)
print(alist)
插入排序（insertsort）
像打扑克牌时的抓牌，第一张牌是不需要插入的，第二张牌开始就需要插入了，根据习惯，这里是从右往左看，小的一直往左边挪，一旦确认位置就退出循环（去抓下一张牌）
package main
import "fmt"
func insertSortAsc(arrayA []int){
for i:=1; i < len(arrayA); i++ {
for j:=i; j > 0; j-- {
fmt.Println(arrayA[j])
if arrayA[j-1] > arrayA[j]{
arrayA[j-1], arrayA[j] = arrayA[j], arrayA[j-1]
} else {
break
}
}
}
fmt.Println(arrayA)
}
func insertSortDesc(arrayA []int){
for i:=1; i < len(arrayA); i++{
for j:=i; j > 0; j--{
if arrayA[j-1] < arrayA[j]{
arrayA[j-1], arrayA[j] = arrayA[j], arrayA[j-1]
} else {
break
}
}
}
fmt.Println(arrayA)
}
func main(){
var arrayA []int = []int{3,1,5,2,9,10,6,4,8,7}
insertSortAsc(arrayA)
insertSortDesc(arrayA)
}
最新文章
- 看懂mysql执行计划--官方文档
- HTML精确定位:scrollLeft,scrollWidth,clientWidth,offsetWidth之完全详解
- [LeetCode] Same Tree
- POJ 2750 Potted Flower (线段树区间合并)
- Eclipse反编译插件JadEclipse 【转】
- 128. Longest Consecutive Sequence
- Python核心编程--学习笔记--6--序列（上）字符串
- [LeetCode]Link List Cycle
- 华为oj 统计字符串不同字符
- Linux系统基础命令
- Elasticsearch head安装
- win8 explorer 进程频繁奔溃的原因及处理
- 服务器获取浏览器发送请求中的cookies，选取自己需要的cookie
- Shell按行读取文件的3种方法
- scrapy中的xpath用法和css的用法
- PostgreSQL Json字段作为查询条件案例
- DDD初探
- bwdist matlab
- poj2763树链剖分边权+区间和
- TZOJ 2722 Matrix(树状数组区间取反单点查询)