要是哪次我冒泡排序没能写出来,直接给自己一巴掌。
冒泡排序
两两交换
冒泡排序的本质就是一个双重循环。有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来实现。用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)
}