冒泡排序

最基本的排序方法之一

要是哪次我冒泡排序没能写出来,直接给自己一巴掌。

冒泡排序的本质就是一个双重循环。有n个元素就需要进行n次排序。若有n个元素,外层循环表示需要进行n-1=i次排序,内层循环则表示从第0个元素开始,需要进行n-1-i次排序。

假设按从小到大开始排序。假设一开始最大值就在开头。先将nums[0]和nums[1]进行比较,此时nums[0]更大,所以和nums[1]进行交换。再将nums[1]和nums[2]进行比较和交换。以此类推直到最开始的nums[0]找不到比它更大的值。那么此时nums[0]已经被排到了数组的末尾。

此时在对剩下的n-1,n-2个元素进行冒泡排序,直到没有可排序的元素。

举个例子,三个元素的数组从大到小排序.以下是每次执行交换的例子:

  • 1,2,3
  • 2,1,3
  • 2,3,1
  • 3,2,1

为啥叫它冒泡排序呢?因为如果是按从小到大排序,大的值会在每次交换的过程中被慢慢的交换到数组尾部。

不过很明显,冒泡排序最差的情况下时间复杂度可以达到O(n2)。因为此时数组中的所有元素都需要经过内部循环的IF条件判断。

用C++和GO来实现。用C++是因为常用。用GO是因为目前正在学GO。

常规的交换直接定义一个新变量就行,当然你也可以用异或来交换。反正思路是一样的。这里分别用常规方法(C++)和异或方法(GO)来实现。

C++(常规)

#include <iostream>
using namespace std;

int main()
{
	int nums[10] = { 0,1,2,3,4,5,6,7,8,9};
	int size = 10;
	for (int i = 0; i < size-1; i++)
	{
		for (int j = 0; j < size-1-i; j++)
		{
			if (nums[j+1] > nums[j])
			{
				int tmp = nums[j];
				nums[j] = nums[j + 1];
				nums[j + 1] = tmp;
			}
		}
	}
	for (int i = 0; i < 10; i++)
	{
		cout << nums[i] << " ";
	}
	cout << endl;
	return 0;
}

GO(异或)

package main

import "fmt"

func main() {
	nums := []int{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
	var size = 10
	for i := 0; i < size-1; i++ {
		for j := 0; j < size-1-i; j++ {
			if nums[j+1] > nums[j] {
				nums[j] = nums[j] ^ nums[j+1]
				nums[j+1] = nums[j] ^ nums[j+1]
				nums[j] = nums[j] ^ nums[j+1]
			}
		}
	}
	fmt.Printf("Sorted array is %d", nums)
}
Subscribe
提醒
0 评论
Inline Feedbacks
View all comments
0
在此留下你的评论x