核心思想

递归算法

代码实现

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))
}

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

// 快速排序 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)
    }
}