排序刷题1(Go)

颜色分类

题目描述

给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。

此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

注意: 不能使用代码库中的排序函数来解决这道题。

示例:

输入: [2,0,2,1,1,0] 输出: [0,0,1,1,2,2]

解题思路

因为数据只有0、1、2，且数据量较少，直接上简单选择排序：每经过一次外层循环，找到最小的数字，进行交换

代码

func sortColors(nums []int)  {
    for i:=0;i<len(nums);i++ {
        min:=i
        for j:=i+1;j<len(nums);j++ {
            if nums[min] > nums[j] {
                 min = j
            }
        }
        if min != i {
            nums[i],nums[min] = nums[min],nums[i]
        }
    }
}

对链表进行插入排序

题目描述

示例 1：输入: 4->2->1->3 输出: 1->2->3->4

示例 2：输入: -1->5->3->4->0 输出: -1->0->3->4->5

解题思想

插入排序在这不在赘述，主要是代码编写

代码

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func insertionSortList(head *ListNode) *ListNode {
    if head == nil || head.Next == nil {
        return head
    }
    //新建一个头节点
    h := new(ListNode)
    h.Next = head
    //每次从头遍历找位置的指针
    pre := h
    //当前指针
    cur := head
    //开始遍历
    for cur.Next != nil {
        //下一结点指针
        lat := cur.Next
        
        if lat != nil && lat.Val < cur.Val {
            //如果下一结点不为空，且小于当前指针，使pre移动到cur的前一个位置
            for pre.Next != lat && pre.Next.Val < lat.Val {
                pre = pre.Next
            }
            //进行换序
            temp := pre.Next
            pre.Next = lat
            cur.Next = lat.Next
            lat.Next = temp
            //复位pre
            pre = h
        }else{
            cur = lat
        }

    }
    return h.Next
}