世界不可能那么远

//希尔排序
func shellSort(arr []int) {
length := len(arr)
for step := length / 2; step > 0; step /= 2 {
for i := step; i < length; i += step {
for j := i; j >= 0; j -= step {
if j > 0 && arr[j] < arr[j-step] {
arr[j-step], arr[j] = arr[j], arr[j-step]
}
}
}
}
}

//冒泡排序
func bubbleSort(arr []int) {
length := len(arr)
for i := 0; i < length; i++ {
for j := 0; j < length-1-i; j++ {
if arr[j] > arr[j+1] {
arr[j], arr[j+1] = arr[j+1], arr[j]
}
}
}
}

//选择排序
func selectSort(arr []int) {
length := len(arr)
for i := 0; i < length; i++ {
for j := i + 1; j < length; j++ {
if arr[i] > arr[j] {
arr[i], arr[j] = arr[j], arr[i]
}
}
}
}

//插入排序
func insertSort(arr []int) {
length := len(arr)
for i := 1; i < length; i++ {
for j := i; j >= 0; j-- {
if j > 0 && arr[j] < arr[j-1]{
arr[j-1], arr[j] = arr[j], arr[j-1]
}
}
}
}

func mergeSort(arr []int) {
temp := make([]int, len(arr))
mergeRecursive(arr, temp, 0, len(arr) - 1)
}

//归并排序
func mergeRecursive(arr []int, result []int, start, end int) {
if start >= end {
return
}
end1 := (end-start)>>1 + start
start1, start2 := start, end1 + 1
mergeRecursive(arr, result, start1, end1)
mergeRecursive(arr, result, start2, end)
k := start
for ; start1 <= end1 && start2 <= end; {
if arr[start1] < arr[start2] {
result[k] = arr[start1]
start1++
} else {
result[k] = arr[start2]
start2++
}
k++
}
for ; start1 <= end1; {
result[k] = arr[start1]
start1++
k++
}
for ; start2 <= end; {
result[k] = arr[start2]
start2++
k++
}
for k = start; k <= end; k++ {
arr[k] = result[k]
}
}

//堆排序
func headSort(arr []int) {
length := len(arr)
for i := length/2 - 1; i >= 0; i-- {
heap(arr, i, length)
}

fmt.Println(arr)
for j := length - 1; j > 0; j-- {
arr[0], arr[j] = arr[j], arr[0]
heap(arr, 0, j)
}
}

func heap(arr []int, start int, length int) {
temp := arr[start]
fmt.Println(start, length, arr)
for i := start*2 + 1; i < length; i = i*2 + 1 {
if i+1 < length && arr[i] < arr[i+1] {
i++
}
if arr[i] > temp {
arr[start], start = arr[i], i
} else {
break
}
}
arr[start] = temp
}

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reverseKGroup(head *ListNode, k int) *ListNode {
    if k <= 1  head == nil  head.Next == nil {
return head
    } 
    start,end,next,oldEnd, count := head,head,head,head, 0
    for loop := 1;end != nil; loop++{
        if loop % k == 0 {
            next,end.Next = end.Next, nil
            newHead := reverseList(start)
            if loop == k {
                head = newHead
            }else{
                oldEnd.Next, oldEnd = newHead, start
            }
            start.Next,start,end = next,next,next
        }else{
            end = end.Next
            count++
        }
    }
    if count % k == 0 {
        reverseList(start)
    }
    return head
}

func reverseList(head *ListNode) *ListNode {
    var prev *ListNode
    for head != nil  {
        head.Next, prev, head = prev, head, head.Next
    }
    return prev
}

func lengthOfLongestSubstring(s string) int {
sLen := len(s)
if sLen <= 1 {
return sLen
}
tempMap := make([]int, 256) // 字符词频表
right := 0
maxLen := 0
for left := 0; left < sLen; left++ {
for ; right < sLen && tempMap[s[right]] == 0; right++ {
tempMap[s[right]]++
}
fmt.Println(tempMap)
maxLen = max(maxLen, right - left)
if right == sLen {
break
}
tempMap[s[left]]--
}
return maxLen
}

func max(x, y int) int {
    if x < y {
        return y
    }
    return x
}

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reverseList(head *ListNode) *ListNode {

    var prev *ListNode
    for head != nil  {
        // next := head.Next
        // head.Next = prev
        // prev = head
        // head = next
        head.Next, prev, head =  prev, head, head.Next
    }
    return prev
}

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reverseList(head *ListNode) *ListNode {


    if head == nil  head.Next == nil {
        return head
    }
    curr := reverseList(head.Next)
    head.Next.Next = head
    head.Next = nil
    return curr
}

func sortArray(nums []int) []int {
    start := 0
    left := 0 
    right := len(nums) - 1
    end := len(nums)
    if left >= right  len(nums) <= 1{
        return nums
    }
    
    pos := (right - left) / 2
    mid := nums[pos]
    nums[left], nums[pos] = nums[pos], nums[left]
    for left < right{
        for nums[right] >= mid && left < right{
            right--
        }
        nums[left], nums[right] = nums[right], nums[left]
        
        for nums[left] <= mid && left < right{
            left++
        }
        nums[left], nums[right] = nums[right], nums[left]
    } 
    
    sortArray(nums[right+1:end])
    sortArray(nums[start:left])
    
    return nums
}