十大排序

交换变量的方式可采用异或（^）（前提是两变量的指向不是同一块地址空间）

原理：

int a=甲; int b=乙;

a=a^b;  //a=a^b=甲^乙;

b=a^b;  //b=a^b=甲^乙^乙=甲;

a=a^b;  //a=a^b=甲^乙^甲=乙;

应用：挑选出一堆数中出现奇数次的一种或两种数

实现原理：将数全部进行异或，出现偶数次的数进行异或得到0，剩下的便是出现奇数次的数，若是有两个出现奇数次的数，则找出两数的异或值为1的那一位，再分离出再那一位为1的数，最后分离出来的数再异或上原始两数的异或值即可.

各排列的复杂度：

（1）选择排序

算法思想

选择排序是一种简单直观的排序算法，无论什么数据进去都是 O(n²) 的时间复杂度。所以用到它的时候，数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。

算法步骤

首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。
再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
重复第二步，直到所有元素均排序完毕。

动图演示

c代码实现

#include <bits/stdc++.h>
using namespace std;

int n;
int a[1000];

void select_sort(int a[],int len){
	for(int i=0; i<len; i++) 
		for(int j=i+1; j<len; j++) 
			if(a[j]<a[i]) swap(a[j],a[i]);
}

int main() {
	scanf("%d",&n);
	for(int i=0; i<n; i++) scanf("%d",&a[i]);
	select_sort(a,n);
	for(int i=0; i<n; i++) printf("%d ",a[i]);
	printf("\n");
    return 0;
}

python代码实现

def SelectSort(arr):
    for i in range(len(arr)-1):
        min_val, pos = arr[i], i
        for j in range(i+1, len(arr)):
            if arr[j] < min_val:
                min_val, pos = arr[j], j
        arr[i], arr[pos] = arr[pos], arr[i]

（2）冒泡排序

算法思想

冒泡排序（Bubble Sort）也是一种简单直观的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢”浮”到数列的顶端。

作为最简单的排序算法之一，冒泡排序给我的感觉就像 Abandon 在单词书里出现的感觉一样，每次都在第一页第一位，所以最熟悉。冒泡排序还有一种优化算法，就是立一个 flag，当在一趟序列遍历中元素没有发生交换，则证明该序列已经有序。但这种改进对于提升性能来说并没有什么太大作用。

算法步骤

1.比较相邻的元素。如果第一个元素比第二个元素大，就交换他们两个。
2.对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
3.针对所有的元素重复以上的步骤，除了最后一个。
4.持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

注：原始的冒泡是从后往前的

动图演示

c代码实现

#include <bits/stdc++.h>
using namespace std;

int n;
int a[1000];

template <typename T>
//整数或浮点数皆可使用
void bubble_sort(T a[],int len) {
    for(int i=0; i<len-1; i++)
        for(int j=0; j<len-1-i; j++)
        	if(a[j]>a[j+1]) swap(a[j],a[j+1]);
}

int main() {
	scanf("%d",&n);
	for(int i=0; i<n; i++) scanf("%d",&a[i]);
	bubble_sort(a,n);
	for(int i=0; i<n; i++) printf("%d ",a[i]);
	printf("\n");
    return 0;
}

python代码实现

def Bubble_Sort(arr):
    for i in range(len(arr)-1):
    	# 如果某一趟排序并没有发生交换,那么可以认为数组有序,终止排序即可。
        flag = False
        for j in range(len(arr)-i-1):
            if arr[j] > arr[j+1]:
                flag = True
                arr[j], arr[j+1] = arr[j+1], arr[j]
        if flag == False:
            break