1.排序的基本介绍
排序是将一组数据，依指定的顺序进行排列的过程。常见的排序：
A.冒泡排序
B.选择排序
C.插入排序
D.快速排序
排序的分类
1）内部排序
指将需要处理的所有数据都加载到内部存储器中进行排序。(包括交换式排序法、选择式排序法和插入式排序法)。
交换式排序法
交换式排序属于内部排序法，是运用数据值比较后，依判断规则对数据位置进行交换，以达到排序的目的。
交换式排序法又可分为两种：冒泡排序法(Bubble sort)、快速排序法(Quick sort)
2）外部排序法
数据量过大，无法全部加载到内存中，需要借助外部存储进行排序。(包括合并排序法和直接合并排序法)。
2.交换式排序法-冒泡排序法
冒泡排序(Bubble Sorting)的基本思想是：通过对待排序序列从后向前(从下标较大的元素开始），依次比较相邻元素的排序码，若发现逆序则交换，使排序码较小的元素逐渐从后部移向前部(从下标较大的单元移向下标较小的单元)，就象水底下的气泡一样逐渐向上冒。
因为排序的过程中，各元素不断接近自己的位置，如果一趟比较下来没有进行过交换，就说明序列有序，因此要在排序过程中设置一个标志flag判断元素是否进行过交换。从而减少不必要的比较(优化)。
举个栗子
将五个无序[24,69,80,57,13]，使用冒泡排序法将其排成一个从小到大的有序数列。
冒泡算法的思路分析
冒泡排序的实现
package main
import "fmt"
func BubbleSort(arr *[5]int){
fmt.Println("排序前arr=",(*arr))
temp := 0 //临时变量，用于交换
// 冒泡排序，双层for循环
for i := 0; i < len(*arr) - 1; i++{
for j := 0; j < len(*arr) - 1 - i; j++{
if (*arr)[j] > (*arr)[j+1]{
// 交换
temp = (*arr)[j]
(*arr)[j] = (*arr)[j+1]
(*arr)[j+1] = temp
}
}
}
fmt.Println("排序后arr=",(*arr))
}
func main(){
// 定义数组
arr := [5]int{24,69,80,57,13}
// 将数组传递给一个函数，完成排序
BubbleSort(&arr)
fmt.Println("main arr=",arr)
}
结果：
3.交换式排序法-快速排序法
快速排序（Quicksort）是对冒泡排序的一种改进。基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
快速排序法示意图
快速排序法应用实例
要求：对[2,10,8,22,34,5,12,28,21,11]进行从小到大的排序，要求使用快速排序法。
验证分析：
1)如果取消左右递归，结果是2 10 8 22 11 5 12 28 21 34
2)如果取消右递归,结果是2 5 8 10 11 22 12 28 21 34
3)如果取消左递归,结果是2 10 8 22 11 5 12 21 28 34
快速排序法的代码实现
package main
import(
"fmt"
)
// /快速排序/说明
// 1. left 表示数组左边的下标
// 2. right表示数组右边的下标
// 3. array表示要排序的数组
func QuickSort(left int,right int, array *[10]int){
l := left
r := right
// mid是中轴，支点
p := array[(left+right)/2]
temp := 0
// for 循环的目标，将比p小的数放到左边，比p大的数放到右边
for ; l < r;{
// 从p的左边找到大于等于p的值
for ; array[l] < p;{
l++
}
// 从p的右边边找到小于等于p的值
for ; array[r] > p; {
r--
}
// r >= l表明本次分解任务完成，break
if l >= r{
break
}
// 交换
temp = array[l]
array[l] = array[r]
array[r] = temp
// 优化
if array[l] == p{
r--
}
if array[r] == p{
l++
}
// 如果l==r，再移动一下
if l == r{
l++
r--
}
// 向左递归
if left < r{
QuickSort(left,r,array)
}
// 向右递归
if right > l{
QuickSort(l,right,array)
}
}
}
func main(){
arr := [10]int{2,10,8,22,34,5,12,28,21,11}
fmt.Println("初始", arr)
// 调用快速排序
QuickSort(0,len(arr)-1,&arr)
fmt.Println("main...",arr)
}
运行结果
4.选择排序法
选择式排序也属于内部排序法，是从欲排序的数据中，按指定的规则选出某一元素，经过和其他元素重整，再依原则交换位置后达到排序的目的。
选择排序思想
选择排序(select sorting)也是一种简单的排序方法。它的基本思想是：第一次从R[0]–R[n-1]中选取最小值，与R[0]交换，第二次从R[1]–R[n-1]中选取最小值，与R[1]交换，第三次从R[2]–R[n-1]中选取最小值，与R[2]交换，…，第i次从R[i-1]–R[n-1]中选取最小值，与R[i-1]交换，…，第n-1次从R[n-2]–R[n-1]中选取最小值，与R[n-2]交换，总共通过n-1次，得到一个按排序码从小到大排列的有序序列。
选择排序的示意图
选择排序应用实例
有一群小老虎，体重分别是10kg，34kg，19kg，100kg，80kg，请用选择排序从高到低进行排序。
代码实现
package main
import "fmt"
func selectSort(array *[5]int){
for j := 0; j < len(array); j++{
max := array[j]
maxIndex := j
for i := j; i < len(array); i++{
if max < array[i]{
max = array[i]
maxIndex = i
}
}
// 交换
if maxIndex != j{
array[j], array[maxIndex] = array[maxIndex], array[j]
}
fmt.Printf("第%d次 %v\n",j+1,*array)
}
}
func main(){
// 10kg，34kg，19kg，100kg，80kg
arr := [5]int{10,34,19,100,80}
fmt.Println("初始", arr)
// 调用选择排序
selectSort(&arr)
fmt.Println("main...",arr)
}
运行结果
5.插入排序
插入式排序属于内部排序法，是对于欲排序的元素以插入的方式找寻该元素的适当位置，以达到排序的目的。
插入排序法思想
插入排序(Insertion Sorting)的基本思想是：把n个待排序的元素看成为一个有序表和一个无序表，开始时有序表中只包含一个元素，无序表中包含有n-1个元素，排序过程中每次从无序表中取出第一个元素，把它的排序码依次与有序表元素的排序码进行比较，将它插入到有序表中的适当位置，使之成为新的有序表。
插入排序的示意图
选择排序应用实例
有一群小老虎，考试成绩分别是23,0,12,56,34，请从小到大排序。
插入排序的代码实现
package main
import "fmt"
func InsertSort(arr *[5]int){
for i := 1; i < len(arr); i++{
insertKey := arr[i]
inserIndex := i-1
// 从大到小
for inserIndex >= 0 && arr[inserIndex] < insertKey{
arr[inserIndex+1] = arr[inserIndex]
inserIndex -- //数据后移
}
// 插入
if inserIndex + 1 != i{
arr[inserIndex+1] = insertKey
}
fmt.Printf("第%d次插入后%v\n",i,*arr)
}
}
func main(){
arr := [5]int{23,0,12,56,34}
fmt.Println("初始", arr)
// 调用插入排序
InsertSort(&arr)
fmt.Println("main...",arr)
}
运行结果
