一、排序

1.1 排序介绍

排序是将一组数据， 依指定的顺序进行排列的过程。排序的分类:

• 1、内部排序:

指将需要处理的所有数据都加载到内部存储器中进行排序。包括(交换式排序法、选择式排序法和插入式排序法);

• 2、外部排序法:

数据量过大，无法全部加载到内存中，需要借助外部存储进行排序。包括(合并排序法和直接合并排序法)。

1.2 交换式排序

交换式排序属于内部排序法，是运用数据值比较后，依判断规则对数据位置进行交换，以达到排序的目的。

交换式排序法可分为两种:

• 1)冒泡排序法(Bubble sort)

• 2)快速排序法(Quick sort)

1.2.1 冒泡排序

冒泡排序( Bubble Sorting) 的基本思想是:通过对待排序序列从后向前(从下标较大的元素开始)，依次比较相.邻元素的排序码，若发现逆序则交换，使排序码较小的元素逐渐从后部移向前部(从下标较大的单元移向下标较小的单元)，就像水底下的气泡一样逐渐向上冒。

因为排序的过程中，各元素不断接近自己的位置，如果一趟比较下来没有进行过交换，就说明序列有序，因此要在排序过程中设置一个标志 flag 判断元素是否进行过交换。从而减少不必要的比较。

案例

以下具体的案例来说明插入法。我们将五个无序:25, 66, 75, 54, 18使用冒泡排序法将其排成一个从小到大的有序数列。

首先有一个数组

• Arr = [25,66,75,54,18]

第一轮比较(外层)

• 1.1 在原始基础上,25 和 66 进行比较; 25<66,所以第一次没有改变 ===》 [25, 66, 75, 54, 18]

• 1.2 在 1.1 基础上,66 和 75 进行比较; 66<75,所以第二次没有改变 ===》 [25, 66, 75, 54, 18]

• 1.3 在 1.2 基础上,75 和 54 进行比较; 75>54,所以第三次改变 ======》 [25, 66, 54, 75, 18]

• 1.4 在 1.3 基础上,75 和 18 进行比较; 75>18,所以第四次改变 ======》 [25, 66, 54, 18, 75]

在第一轮比较中，进行了 4 次比较得到===>[25, 66, 54, 18, 75]，确定最大数

第二轮比较(外层),在第一轮基础上

• 2.1 在 1.4 基础上,25 和 66 进行比较; 25<66,所以第一次没有改变 ===》 [25, 66, 54, 18, 75]

• 2.2 在 2.1 基础上,66 和 54 进行比较; 66>54,所以第二次改变 ======》 [25, 54, 66, 18, 75]

• 2.3 在 2.2 基础上,66 和 18 进行比较; 66>18,所以第三次改变 ======》 [25, 54, 18, 66, 75]

在第二轮比较中，进行了 3 次比较得到===>[25, 54, 18, 66, 75]

第三轮比较(外层),在第二轮基础上

• 3.1 在 2.3 基础上,25 和 54 进行比较; 25<54,所以第一次没有改变 ===》 [25, 54, 18, 66, 75]

• 3.2 在 2.1 基础上,54 和 18 进行比较; 54>18,所以第二次改变 ======》 [25, 18, 54, 66, 75]

在第三轮比较中，进行了 2 次比较得到===>[25, 18, 54, 66, 75]

第四轮比较(外层),在第三轮基础上

• 4.1 在 3.2 基础上,25 和 18 进行比较; 25>18,所以第一次改变 ===》 [18, 25, 54, 66, 75]

在第四轮比较中，进行了 1 次比较得到===>[18, 25, 54, 66, 75]

冒泡排序规则-总结：

• 一共会经过 数组长度-1轮比较，每一轮将会确定一个数的位置

• 每一轮的比较次数逐渐减少

• 前面一个数比后面一个数大时，进行交换

1.2.2 冒泡排序代码实现 -- 方式一(内部 for 循环不同)

package main
import "fmt"
// 冒泡排序函数func bubbleSort(arr *[5]int) {  // 排序前  // soft befor arr =  [25 66 75 54 18]  fmt.Println("soft befor arr = ", *arr)  // 定义中间临时变量  temp := 0
  // 外层轮  for i := len(arr) - 1; i > 0; i-- {    // 内层次数    for j := 0; j < i; j++ {      // 比较大小      if (*arr)[j] > (*arr)[j+1] {        temp = (*arr)[j]        (*arr)[j] = (*arr)[j+1]        (*arr)[j+1] = temp      }    }  }  fmt.Println("Sorted arr = ", *arr)}
func main() {
  // 声明数组  arr := [5]int{25, 66, 75, 54, 18}        // 将数组传递给函数  bubbleSort(&arr)  // soft befor arr =  [25 66 75 54 18]  // Sorted arr =  [18 25 54 66 75]}

1.2.3 冒泡排序代码实现 -- 方式一(内部 for 循环条件不同)

package main
import "fmt"
// 冒泡排序函数func bubbleSort(arr *[5]int) {  // 排序前  // soft befor arr =  &[25 66 75 54 18]  fmt.Println("soft befor arr = ", *arr)  // 定义中间临时变量  temp := 0
  // 外层轮  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("Sorted arr = ", *arr)}
func main() {
  // 声明数组  arr := [5]int{25, 66, 75, 54, 18}  // 将数组传递给函数  bubbleSort(&arr)  // soft befor arr =  [25 66 75 54 18]  // Sorted arr =  [18 25 54 66 75]
}