冒泡排序,直接选择排序,直接插入排序
#include<iostream>using namespace std;//show arrayvoid show(int *ar, int len){for(int i=0; i<len; ++i){cout<<ar[i]<<" ";}cout<<endl;}//bubbleSort//冒泡排序是一种稳定的排序算法//最好时间复杂度为O(n)平均时间复杂度为O(n^2)最坏时间复杂度为O(n^2)//空间复杂度为O(1)void bubbleSort(int *ar, int len){bool flag = true;//使用标记可以是有序序列排序时间复杂度为O(n)for(int i=0; i<len-1&&flag; ++i){for(int j=0; j<len-1-i; ++j){flag = false;if(ar[j] > ar[j+1]){ar[j] ^= ar[j+1];ar[j+1] ^= ar[j];ar[j] ^= ar[j+1];flag = true;}}}}//selectSort//直接选择排序不稳定 最好最坏平均时间复杂度都是O(n^2) 空间复杂度O(1) void selectSort(int *ar, int len){for(int i=0; i<len-1; ++i){//假设第i个元素最小,以此类推int min = i;for(int j=i+1; j<len; ++j){if(ar[j] < ar[min]){min = j;}}//如果第i个不是最小,把最小的交换到第一个 以此类推if(i != min){ar[i] ^= ar[min];ar[min] ^= ar[i];ar[i] ^= ar[min];}}}//insertSort //直接插入排序为稳定排序//最好时间复杂度O(n) 最坏时间复杂度O(n^2) 平均时间复杂度O(n^2)//直接插入排序的特点是待排序数组越有序速度越快//空间复杂度为O(1)void insertSort(int *ar, int len){for(int i=1; i<len; ++i){int temp = ar[i];//从后向前比较(有序数组可以保证时间复杂度为O(n)) 在合适的位置插入 int j = i-1;for(j; j>=0; –j){if(ar[j] > temp){ar[j+1] = ar[j];}else{break;}}ar[j+1] = temp;}}int main(void){int ia[] = {45,56,78,9,23,45,12,99,82,65,3000,};int len =sizeof(ia)/sizeof(ia[0]);//bubbleSort(ia, len);//selectSort(ia, len);//insertSort(ia, len);show(ia, len);return 0;}
，天才就是这样，终身努力，便是天才。
