10 examples of 'speed of quick sort' in Go

13
func heapsort(array []int) {
14
	ep := (len(array) - 1) >> 1
15
	fmt.Println(ep)
16
	for i := ep; i >= 0; i-- {
17
		heapt(array, i, len(array)-1)
18
	}
19
20
	for i := len(array) - 1; i > 0; i-- {
21
		array[0], array[i] = array[i], array[0]
22
		heapt(array, 0, i-1)
23
	}
24
}

5
func BubbleSort(arr []int) []int {
6
	if len(arr) == 0 {
7
		return arr
8
	}
9
	for j := len(arr); j > 0; j-- {
10
		for i := 1; i < j; i++ {
11
			if arr[i] > arr[i+1] {
12
				swap(arr, i, i+1)
13
			}
14
		}
15
	}
16
	return arr
17
}

22
func BubbleSort(arr []int) []int {
23
	tmp := 0
24
	for i := 0; i < len(arr); i++ {
25
		for j := 0; j < len(arr)-i-1; j++ {
26
			if arr[j] > arr[j+1] {
27
				tmp = arr[j]
28
				arr[j] = arr[j+1]
29
				arr[j+1] = tmp
30
			}
31
		}
32
	}
33
	return arr
34
}

33
func heapSort(s1 []int, i int, s1Len int) []int {
34
	done := false
35
36
	tmp := 0
37
	maxChild := 0
38
39
	for (i*2+1 < s1Len) && (!done) {
40
		if i*2+1 == s1Len-1 {
41
			maxChild = i*2 + 1
42
		} else if s1[i*2+1] > s1[i*2+2] {
43
			maxChild = i*2 + 1
44
		} else {
45
			maxChild = i*2 + 2
46
		}
47
48
		if s1[i] < s1[maxChild] {
49
			tmp = s1[i]
50
			s1[i] = s1[maxChild]
51
			s1[maxChild] = tmp
52
			i = maxChild
53
		} else {
54
			done = true
55
		}
56
		fmt.Printf("Sorting ...:\t%v\n", s1)
57
	}
58
59
	return s1
60
}

62
func (tags FastTags) sortQuick() {
63
	tags.sortQuick_r(0, len(tags.Slice)-1)
64
}

22
func BubbleSort(arr []int) {
23
	n := len(arr)
24
	for i := 0; i < n; i++ {
25
		flag := false
26
		for j := 0; j < n - i - 1; j++ {
27
			if arr[j] > arr[j + 1] {
28
				tmp := arr[j]
29
				arr[j] = arr[j + 1];
30
				arr[j + 1] = tmp
31
				flag = true
32
			}
33
		}
34
		if (!flag) {
35
			break;
36
		}
37
	}
38
}

30
func quickSortUtil(arr []int, lower int, upper int) {
31
	if upper <= lower {
32
		return
33
	}
34
	pivot := arr[lower]
35
	start := lower
36
	stop := upper
37
38
	for lower < upper {
39
		for arr[lower] <= pivot && lower < upper {
40
			lower++
41
		}
42
		for arr[upper] > pivot && lower <= upper {
43
			upper--
44
		}
45
		if lower < upper {
46
			swap(arr, upper, lower)
47
		}
48
	}
49
	swap(arr, upper, start) // upper is the pivot position
50
	quickSortUtil(arr, start, upper-1) // pivot -1 is the upper for left sub array.
51
	quickSortUtil(arr, upper+1, stop)  // pivot + 1 is the lower for right sub array.
52
}

17
func sortList(head *ListNode) *ListNode {
18
	length := 0
19
	cur := head
20
	for cur != nil {
21
		length++
22
		cur = cur.Next
23
	}
24
	if length <= 1 {
25
		return head
26
	}
27
28
	middleNode := middleNode(head)
29
	cur = middleNode.Next
30
	middleNode.Next = nil
31
	middleNode = cur
32
33
	left := sortList(head)
34
	right := sortList(middleNode)
35
	return mergeTwoLists(left, right)
36
}

6
func GnomeSort(arr []int) []int {
7
    for pos := 1; pos < len(arr); pos++ {
8
        if arr[pos] >= arr[pos-1] {
9
            continue
10
        } else {
11
            arr[pos], arr[pos-1] = arr[pos-1], arr[pos]
12
            if pos > 1 {
13
                pos -= 1
14
            }
15
        }
16
        pos -= 1
17
    }
18
19
    return arr
20
}

84
func quickSort2(nums []int) {
85
	if nums == nil || len(nums) == 0 {
86
		return
87
	}
88
89
	quickSortBody2(nums, 0, len(nums)-1)
90
}