写给你的快速排序，请签收~

喜欢ヅ旅行 2023-07-19 10:43 16阅读 0赞

###        黄昏时偷来你的肋骨酿酒   百年后醉的有血有肉  ###

## ##

**目录**

原理

举例

代码实现

--------------------

## 原理 ##

快速排序是冒泡排序的改进，思想是分治法。也是通过不断比较和交换元素实现排序（每次逻辑取一个基准元素，每个基准元素参与多次循环和其他元素的交换），在排序时将较大的元素从前面直接放到基准元素的后面，将较小的元素放到基准元素的前面，每次逻辑执行完时左子序列的所有元素均小于右子序列的所有元素，也就是进行了分区操作，然后继续对左右子序列分别执行该逻辑（递归）以此类推。

上述过程中，“该逻辑”就是一次递归的过程。

## 举例 ##

示例数组：\{11, 3, 6, 25, 15, 1, 27\}

设置基准元素base设置为data\[0\]，设置两个指针分别从首部和尾部开始移动，进行循环遍历，当当前元素值>base时，当前元素和data\[right\]交换，即移动该元素到基准元素的右侧，当当前元素值<base时，当前元素和data\[left\]交换，即移动该元素到基准元素的左侧...

具体过程依次如下：

原：**11, 3, 6, 25, 15, 1, 27     base=11,left=0,right=5,当前元素arr\[i\]=3，3<11，3和11即3和data\[left\]交换：**

第一次逻辑：

**3, 11, 6,  25, 15, 1, 27**

**3, 6, 11,  25, 15, 1, 27**

**3, 6, 11,  27, 15, 1, 25**

**3, 6, 11, 1, 15,  27, 25**

**3, 6, 1, 11, 15,  27, 25**

第一次逻辑结束，开始分区递归，左序列：3, 6, 1，base=3；右序列：15, 27, 25，base=15。

左侧开始执行递归逻辑：

左侧第一次：**3, 1, 6**

左侧第二次：**1, 3, 6**

右侧开始执行递归逻辑：

右侧第一次：**15, 25, 27 **   注意细节避免无意义操作，如27和自己进行交换。

从上述过程来看，整个执行了8次数据交换。

## 代码实现 ##

package main
    
    import "fmt"
    
    var count int    // 计算交换次数
    
    func quickSort3(arr []int) []int {
    	if len(arr) <= 1 {
    		return arr
    	}
    	base := arr[0]               // 将数组的第一个元素定义为基准比较元素
    	left, right := 0, len(arr)-1 // 两个指针
    	for i := 1; i <= right; {
    		if arr[i] > base {
    			if i != right { // 自己和自己就不用交换了，该判断可有效减少不必要的交换
    				// 将大于比较元素的放到右边
    				arr[i], arr[right] = arr[right], arr[i]
    				count++
    			}
    			right--
    		} else {
    			if i != left {
    				// 将数组中小于比较元素的数放到左边
    				arr[i], arr[left] = arr[left], arr[i]
    				count++
    			}
    			left++
    			i++
    		}
    	}
    
    	quickSort3(arr[:left])
    	quickSort3(arr[left+1:])
    	return arr
    }
    
    func main() {
    	var sortArray = []int{11, 3, 6, 25, 15, 1, 27}
    	fmt.Println("排序前：", sortArray)
    	quickSort3(sortArray)
    	fmt.Println("排序后：", sortArray)
    	fmt.Printf("共发生数据交换：%d 次", count)
    }

控制台

排序前： [11 3 6 25 15 1 27]
    排序后： [1 3 6 11 15 25 27]
    共发生数据交换：8 次
    Process finished with exit code 0