数据结构时间复杂度、冒泡排序、选择排序、插入排序
时间复杂度的计算方式：
1、O(1)：常数
只要没有循环语句，不论代码有多少行，时间复杂度都是O(1)。
2、O(log2n)：对数复杂度，底数不一定是2，可以是任何数
int i = 20;while(i < n){i = i * 2;}
3、O(n)：线性阶
for(int i = 0; i < n; i++){}
4、O(nlogn) : 线性对数阶
for(int i = 0; i < n; i++){int j = 20;while(j < n){i = i * 2;}}
5、O(n2) : 平方阶
for(int i = 0; i < n; i++){for(int j = 0 ; j < n;j ++){}}
1
冒泡排序：其时间复杂度为O(n2)
原理：从左往右依次进行对比，如果左边比右边大就进行交换，第一次交换后会将最后一个放置为最大的元素。然后依次，再将倒数第二个元素放置为次之的元素。下面兑现代码：
Java实现：
import java.text.SimpleDateFormat;import java.util.Date;/*** @Author junkle* @Date 2020/4/21 - 16:02* @Version 1.0**/public class BubbleSort {public static void main(String[] args) {final int MAXSIZE = 80000;//这是一个即将要排序得数组int[] arr = new int[MAXSIZE];for (int i = 0;i < MAXSIZE;i++){arr[i] = (int) (Math.random() * 70000 % 101);}Date date = new Date();SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd hh：mm：ss");String format1 = simpleDateFormat.format(date);System.out.println("排序前的时间是" + format1);// for (int i : arr){// System.out.print(i + " ");// }// System.out.println();bSort(arr);// for (int i : arr){// System.out.print(i + " ");// }Date date1 = new Date();String format = simpleDateFormat.format(date1);System.out.println("排序后的时间是" + format);}public static void bSort(int[] array){int size = array.length;for (int i = 0; i < size - 1 ; i++){for (int j = 0; j < size - 1 - i; j++){if (array[j] > array[j + 1]){int tmp = array[j + 1];array[j + 1] = array[j];array[j] = tmp;}}}}}
C++实现：
using namespace std;constexpr int MAXSIZE = 80000;void bSort(int* array, int size){int tmp = 0;for (int i = 0; i < size - 1; i++) {//cout << "即将进行第 " << i + 1 <<" 次排序..."<< endl;bool flag = false;for (int j = 0;j < size - 1 - i;j++){if (array[j] > array[j + 1]){flag = true;tmp = array[j];array[j] = array[j + 1 ];array[j + 1] = tmp;}}if (!flag){break;}}}int mainmp(){srand(time(NULL));int* array = new int[MAXSIZE];for (int i = 0; i < MAXSIZE; i++){array[i] = rand() * 70000 % 101;}/*for (int i = 0; i < MAXSIZE; i++){cout << array[i] << " ";}*/cout << endl;cout << "排序之前的时间是：";time_t start = clock();cout << start;cout << endl;bSort(array, MAXSIZE);cout << "排序之后的时间是是：";time_t end = clock();cout << end << endl;/*for (int i = 0; i < MAXSIZE; i++){cout << array[i] << " ";}*/cout << endl;return 0;}
2
选择排序
原理：选择出最小的与第一个进行交换，选择次小和第二个元素进行交换。依次..... 其时间复杂度为O(n2) 。下面看兑现代码：
Java实现：
import javax.imageio.stream.ImageInputStreamImpl;import java.text.SimpleDateFormat;import java.util.Date;import java.util.zip.CheckedOutputStream;/*** @Author junkle* @Date 2020/4/21 - 18:30* @Version 1.0**/public class SelectSort {public static void sort(int[] array){int size = array.length;int min = 0;int index = 0;for (int i = 0; i < size; i++){min = array[i];index = i;for (int j = i + 1; j < size;j++){if (min > array[j]){min = array[j];index = j;}}if (index != i) {array[index] = array[i];array[i] = min;}}}public static void main(String[] args) {final int MAXSIZE = 8;//这是一个即将要排序得数组int[] arr = new int[MAXSIZE];for (int i = 0;i < MAXSIZE;i++){arr[i] = (int) (Math.random() * 70000 % 101);}Date date = new Date();SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd hh：mm：ss");String format1 = simpleDateFormat.format(date);System.out.println("排序前的时间是" + format1);for (int i : arr){System.out.print(i + " ");}System.out.println();sort(arr);for (int i : arr){System.out.print(i + " ");}Date date1 = new Date();String format = simpleDateFormat.format(date1);System.out.println("排序后的时间是" + format);}}
C++实现：
using namespace std;constexpr int MAXSIZE = 80000;void chooseSort(int *array,int size){int tmp = 0;int minIndex = 0;for (int i = 0; i < size - 1; i++){tmp = array[i];minIndex = i;for (int j = i + 1; j < size; j++){if (tmp > array[j]){tmp = array[j];minIndex = j;}}if (minIndex != i){array[minIndex] = array[i];array[i] = tmp;}}}int mainxz(){srand(time(NULL));int* array = new int[MAXSIZE];for (int i = 0; i < MAXSIZE; i++){array[i] = rand() % 101;}/*for (int i = 0; i < MAXSIZE; i++){cout << array[i] << " ";}*/cout << endl;cout << "排序之前的时间是：";time_t start = clock();cout << start;cout << endl;chooseSort(array, MAXSIZE);cout << "排序之后的时间是是：";time_t end = clock();cout << end << endl;/*for (int i = 0; i < MAXSIZE; i++){cout << array[i] << " ";}*/cout << endl;delete []array;return 0;}
3
插入排序
原理：从第二个元素开始依次向回查找该元素合适插入的位置。需要用一个变量来记录要插入的元素，然后如果元素不适合，依次向后排。其时间复杂度为O(n2)
下面看对兑现代码：
Java实现：
import java.util.SortedMap;/*** @Author junkle* @Date 2020/4/21 - 21:55* @Version 1.0**/public class InsertSort {public static void main(String[] args) {int[] array = new int[]{1,8,-1,10,2};for (int i = 0; i < 5;i++){System.out.print(array[i] + " ");}System.out.println();sort(array);for (int i = 0; i < 5;i++){System.out.print(array[i] + " ");}System.out.println();}public static void sort(int[] array){int size = array.length;int insertValue = 0;int insertIndex = 0;for (int i = 1; i < size; i++){insertValue = array[i];insertIndex = i - 1;while (insertIndex >= 0 && insertValue < array[insertIndex]){array[insertIndex + 1] = array[insertIndex];insertIndex--;}if (insertIndex != i - 1){array[insertIndex + 1] = insertValue;}}}}
C++实现：
constexpr int MAXSIZE = 80000;using namespace std;void insertSort(int* array, int size){for (int i = 1; i < size; i++){int insertValue = array[i];int insertIndex = i - 1;while (insertIndex >= 0 && insertValue < array[insertIndex]){array[insertIndex + 1] = array[insertIndex];insertIndex--;}if (insertIndex != i - 1){array[insertIndex + 1] = insertValue;}}}int main(){srand(time(NULL));int* array = new int[MAXSIZE];for (int i = 0; i < MAXSIZE; i++){array[i] = rand() * 70000 % 101;}/*for (int i = 0; i < MAXSIZE; i++){cout << array[i] << " ";}*//*cout << endl;*/cout << "排序之前的时间是：";time_t start = clock();cout << start;cout << endl;insertSort(array, MAXSIZE);cout << "排序之后的时间是是：";time_t end = clock();cout << end << endl;//for (int i = 0; i < MAXSIZE; i++)//{// cout << array[i] << " ";//}cout << endl;return 0;}