go语言数据结构[1]--go实现快速排序的两种方式

前言

go实现快速排序的两种方式。借助Go语言slice本身的特点以及切割时的特性,在快速排序递归时,参数不用传递开始与结尾参数。

快速排序第一种方式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
/*
Copyright © 2018 jonson
*/
package main
import "fmt"
//打印
func show(arr []int){
for i:=0;i<len(arr);i++{
fmt.Println(arr[i])
}
fmt.Println("----------------------------------------------")
}

func main(){
k := []int{1,3,2,4,9,2,6,5,4,8}
show(k)
quicksort(k)
show(k)
}

func quicksort(arr []int){

if len(arr) >1{//必须要长度大于1才有意义。

end := len(arr)
i := 0
j := len(arr)

for i<j{
for i < end-1{
i++
if arr[i] <= arr[0]{
break
}
}

for j>0{
j--
if arr[j]>=arr[0]{
break
}
}
//如果i<j,说明要将这两个元素交换
if i < j{
temp :=arr[i]
arr[i] = arr[j]
arr[j] = temp
}
}

//交换start和 j 。 到此为止, j之前为小于start元素的,j之后为大于start元素的。
tmp := arr[j]
arr[j] = arr[0]
arr[0] = tmp

//递归下去
if j >0 {
quicksort(arr[0:j])
}

if j+1 < end{
quicksort(arr[j+1:end])
}
}
}

快速排序第二种方式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
/*
Copyright © 2018 jonson
*/
package main
import "fmt"
//打印
func show(arr []int){
for i:=0;i<len(arr);i++{
fmt.Println(arr[i])
}
fmt.Println("----------------------------------------------")
}

func main(){
k := []int{1,3,2,4,9,2,6,5,4,8}
show(k)
quicksort(k)
show(k)
}

func quicksort(arr []int){

if len(arr) >1{//必须要长度大于1才有意义。

end := len(arr)
i := 0
j := len(arr)

for i<j{
for i < end-1{
i++
if arr[i] <= arr[0]{
break
}
}

for j>0{
j--
if arr[j]>=arr[0]{
break
}
}
//如果i<j,说明要将这两个元素交换
if i < j{
temp :=arr[i]
arr[i] = arr[j]
arr[j] = temp
}
}

//交换start和 j 。 到此为止, j之前为小于start元素的,j之后为大于start元素的。
tmp := arr[j]
arr[j] = arr[0]
arr[0] = tmp

//递归下去
if j >0 {
quicksort(arr[0:j])
}

if j+1 < end{
quicksort(arr[j+1:end])
}
}
}

c语言实现1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include<stdio.h>
#include<stdlib.h>
//打印
void show(int *a,int length)
{
for (int i = 0; i < length; i++)
{
printf("%d\n", a[i]);
}
printf("---------------------------\n");
}
//快速排序,不仅要写出来,而且要优美

//arr 为数组
//start 为开始的元素的下标
//end 为结束的元素的下标+1
void quick_sort(int *arr, int start, int end)
{
if (start < end) //必须要开始的元素 <结束的元素才有意义。
{
//赋值
int i = start;
int j = end;

//i在++,j在--。第一个do为当i<j时就继续下去。
do
{
do //此do一直让i++,直到,发现大于start的
{
i++;
} while (i < end && arr[i] < arr[start]);

do//此do一直让j--,直到,发现小于start的元素
{
j--;
} while (j>start && arr[j]>arr[start]);
//如果i<j,说明要将这两个元素交换
if (i < j)
{
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
} while (i<j);
//交换start和 j 。 到此为止, j之前为小于start元素的,j之后为大于start元素的。
int temp = arr[j];
arr[j] = arr[start];
arr[start] = temp;

//递归下去
quick_sort(arr, start, j);
quick_sort(arr, j + 1, end);
}
}
void main()
{
int a[10] = { 1,3,2,4,9,2,6,5,4,8 };
show(a, 10);
quick_sort(a, 0,10);
show(a, 10);
system("pause");
}

c语言实现2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include<stdio.h>
#include<stdlib.h>
//打印
void show(int *a,int length)
{
for (int i = 0; i < length; i++)
{
printf("%d\n", a[i]);
}
printf("---------------------------\n");
}
//快速排序,不仅要写出来,而且要优美

//arr 为数组
//start 为开始的元素的下标
//end 为结束的元素的下标+1
void quick_sort2(int *arr, int start, int end)
{
if (start < end) { //start < end 才有进新下去的意义。
//i从第一个开始,记录下标。
int i = start;
//从第二个元素开始,循环到末尾
for (int j = start+1; j < end; j++)
{
//一旦发现比其start小的
if (arr[j] > arr[start])
{
//i++,很重要的一步,也就是让发现的小于start的数,依次放置在第2个,第3个....位置上。
i++;
//交换
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
////交换start和i 。 到此为止, i之前为小于start元素的,i之后为大于start元素的。
int temp = arr[i];
arr[i] = arr[start];
arr[start] = temp;
//递归
quick_sort2(arr, start, i);
quick_sort2(arr, i+1, end);
}
}
void main()
{
int a[10] = { 1,3,2,4,9,2,6,5,4,8 };
show(a, 10);
quick_sort2(a, 0,10);
show(a, 10);
system("pause");
}

JavaScript 语言实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
function quickSort(arr) {  
if (arr.length <= 1) {
return arr;
}  
var pivotIndex = Math.floor(arr.length / 2);  
var pivot = arr.splice(pivotIndex, 1)[0];  
var left = [];  
var right = [];  
for (var i = 0; i < arr.length; i++) {    
if (arr[i] < pivot) {      
left.push(arr[i]);    
} else {      
right.push(arr[i]);    
}  
}  
return quickSort(left).concat([pivot], quickSort(right));
}

JavaScript 语言实现2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
//上面简单版本的缺点是,它需要Ω(n)的额外存储空间,也就跟归并排序一样不好。额外需要的存储器空间配置,在实际上的实现,也会极度影响速度和高速缓存的性能。

function quickSort(array) {
// 交换元素位置
function swap(array, i, k) {
var temp = array[i];
array[i] = array[k];
array[k] = temp;
}
// 数组分区,左小右大
function partition(array, left, right) {
var storeIndex = left;
var pivot = array[right]; // 直接选最右边的元素为基准元素
for (var i = left; i < right; i++) {
if (array[i] < pivot) {
swap(array, storeIndex, i);
storeIndex++; // 交换位置后,storeIndex 自增 1,代表下一个可能要交换的位置
}
}
swap(array, right, storeIndex); // 将基准元素放置到最后的正确位置上
return storeIndex;
}
function sort(array, left, right) {
if (left > right) {
return;
}
var storeIndex = partition(array, left, right);
sort(array, left, storeIndex - 1);
sort(array, storeIndex + 1, right);
}
sort(array, 0, array.length - 1);
return array;
}

JavaScript 语言实现3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
function quickSort(arr) {
return sort(arr, 0, arr.length - 1);
function swap(arr, i, k) {
var temp = arr[i];
arr[i] = arr[k];
arr[k] = temp;
}
function sort(arr, start, end) {
sort(arr, 0, arr.length - 1);
return arr;
function swap(arr, i, k) {
var temp = arr[i];
arr[i] = arr[k];
arr[k] = temp;
}
function sort(arr, start, end) {
if (start >= end) return;
var pivot = arr[start],
i = start + 1,
k = end;
while (true) {
while (arr[i] < pivot) {
i++;
}
while (arr[k] > pivot) {
k--;
}
if (i >= k) {
break;
}
swap(arr, i, k);
}
swap(arr, start, k);
sort(arr, start, Math.max(0, k - 1));
sort(arr, Math.min(end, k + 1), end);
}
}
}