使用go递归快排

- 日理万妓 2023-06-23 09:56 38阅读 0赞

### 使用go递归快排 ###

*  核心思想
 *   *  代码实现

# 核心思想 #

递归算法

## 代码实现 ##

func quickSort(front, rear int, array []int) { 
    	left := front
    	right := rear
    	pivot := array[(front+rear)/2]
    	for left < right { 
    		for array[left] > pivot { 
    			left++
    		}
    		for array[right] < pivot { 
    			right--
    		}
    		if left >= right { 
    			break
    		}
    		array[left], array[right] = array[right], array[left]
    		if array[right] == pivot { 
    			left++
    		}
    		if array[left] == pivot { 
    			right--
    		}
    	}
    	if left == right { 
    		left++
    		right--
    	}
    	if rear > left { 
    		quickSort(left, rear, array)
    	}
    	if front < right { 
    		quickSort(front, right, array)
    	}
    }
    // 快速排序 200000万的数据量运行1s内
    func TestQuickSort(t *testing.T) { 
    	var arr []int
    	var maxSize = 10
    	nowTime1 := time.Now().Unix()
    	rand.Seed(time.Now().Unix())
    	for i := 0; i < maxSize; i++ { 
    		n := rand.Int() % 100
    		arr = append(arr, n)
    	}
    	t.Log("size:", len(arr), "quick 原数据", arr)
    	quickSort(0, len(arr)-1, arr)
    	nowTime2 := time.Now().Unix()
    	t.Log("修改后 :", arr, "耗时:", nowTime2-nowTime1, "size:", len(arr))
    }

以上代码测试结果输出如下，从大到小排序  
![在这里插入图片描述][20191218143845224.png]  
如果是从小到大呢？只需要改动两个地方即可,口水话少说，上代码

// 快速排序 200000万的数据量运行1s内
    func TestQuickSort(t *testing.T) { 
    	var arr []int
    	var maxSize = 10
    	nowTime1 := time.Now().Unix()
    	rand.Seed(time.Now().Unix())
    	for i := 0; i < maxSize; i++ { 
    		n := rand.Int() % 100
    		arr = append(arr, n)
    	}
    	t.Log("size:", len(arr), "quick 原数据", arr)
    	quickSort(0, len(arr)-1, arr)
    	nowTime2 := time.Now().Unix()
    	t.Log("修改后 :", arr, "耗时:", nowTime2-nowTime1, "size:", len(arr))
    }
    
    // 快排使用递归
    func quickSort(front, rear int, array []int) { 
    	left := front
    	right := rear
    	pivot := array[(front+rear)/2]
    	for left < right { 
    		for array[left] < pivot { 
    			left++
    		}
    		for array[right] > pivot { 
    			right--
    		}
    		if left >= right { 
    			break
    		}
    		array[left], array[right] = array[right], array[left]
    		if array[right] == pivot { 
    			left++
    		}
    		if array[left] == pivot { 
    			right--
    		}
    	}
    	if left == right { 
    		left++
    		right--
    	}
    	if rear > left { 
    		quickSort(left, rear, array)
    	}
    	if front < right { 
    		quickSort(front, right, array)
    	}
    }

结果输出如下:  
![在这里插入图片描述][20191218144242195.png]

[20191218143845224.png]: https://img-blog.csdnimg.cn/20191218143845224.png
[20191218144242195.png]: https://img-blog.csdnimg.cn/20191218144242195.png