插入&選擇&快速排序

//選擇排序
func SelectSort(array *[6]int) {
	for j := 0; j < len(array)-1; j++ {
		min := array[j]
		minIndex := j
		//尋找最小的下標
		for i := j + 1; i < len(array); i++ {
			if min > array[i] {
				min = array[i]
				minIndex = i
			}
		}
		if minIndex != j {
			array[j], array[minIndex] = array[minIndex], array[j]
		}
		fmt.Printf("第%d次交換後 %v\n", j+1, *array)
	}

}

//插入排序
func InsertSort(arr *[6]int) {
	for j := 1; j < len(arr); j++ {
		//給第二個元素找位置
		insertVal := arr[j]
		insertIndex := j - 1 //下標
		//由大到小
		for insertIndex >= 0 && arr[insertIndex] < insertVal {
			arr[insertIndex+1] = arr[insertIndex] //數據後移
			insertIndex--
		}
		//插入
		if insertIndex+1 != j {
			arr[insertIndex+1] = insertVal
		}
		fmt.Printf("第%d次插入後 %v\n", j, *arr)
	}

}

//快速排序
func QuickSort(left int, right int, array *[6]int) {
	l := left
	r := right
	pivot := array[(left+right)/2] //中軸

	//比pivot小就放到左邊，反之亦然
	for l < r {
		for array[l] < pivot {
			l++
		}
		for array[r] > pivot {
			r--
		}
		if l >= r { //表示分割完成
			break
		}
		//如果沒完成就交換
		array[l], array[r] = array[r], array[l]
		//改善
		if array[l] == pivot {
			r--
		}
		if array[r] == pivot {
			l++
		}
	}
	//防卡住
	if l == r {
		l++
		r--
	}
	if left < r {
		QuickSort(left, r, array)
	}
	if right > l {
		QuickSort(l, right, array)
	}

}

func main() {
	// var array = [6]int{10, 34, 19, 100, 80, -5}
	// // SelectSort(&array)
	// // InsertSort(&array)
	// // fmt.Println(array)
	// QuickSort(0, len(array)-1, &array)
	// fmt.Println(array)

}

上次修改於 2021-09-01