算法day01之排序算法1

按照稳定性排序算法可以分为稳定排序算法和不稳定排序算法

稳定排序算法有：

1，插入排序（insertion sort）— O(n2)

2，冒泡排序（bubble sort） — O(n2)

3，归并排序（merge sort）— O(n log n); 需要 O(n) 额外存储空间

4，二叉树排序（Binary tree sort） — O(nlogn); 需要 O(n) 额外存储空间

5，计数排序(counting sort) — O(n+k); 需要 O(n+k) 额外存储空间，k为序列中Max-Min+1

6，桶排序（bucket sort）— O(n); 需要 O(k) 额外存储空间

不稳定排序算法：

1，选择排序（selection sort）— O(n2)

2，快速排序（quicksort）— O(nlogn) 平均时间, O(n2) 最坏情况; 对于大的、乱序串列一般认为是最快的已知排序

3，堆排序 （heapsort）— O(nlogn)

4，希尔排序 （shell sort）— O(nlogn)

5，基数排序（radix sort）— O(n·k); 需要 O(n) 额外存储空间 （K为特征个数）

java代码实现如下：

插入排序：将后一个数和前面已经排好的数从后往前以次比较，如果小于前面的数就交换位置，每次排序生成一个有序的数组在最前面

/**
	 * @author sherlock
	 * 插入排序
	 * 时间复杂度平均情况下为n的平方
	 */
	public static void insertSort(int[] arr){
		for(int i = 1;i<arr.length;i++){
			int temp = arr[i];//temp = 9;
			int j = i-1; //j = 0;
			while(j>=0&&temp<arr[j]){  //temp是待排序数，arr[j]是前面以排序数
				arr[j+1] = arr[j]; //如果待排序数西域了前面已经排好序的最后一个数，排好序的最后一个数后移一位，再继续比较，直到待排序数大于了有序数组中的某一个数，跳出循环
				j--;
			}
			arr[j+1] = temp;//将待排序数放到最后一个比他大的数的位置上
		}
	}

冒泡排序：每一次都比较相邻的两个数，如果后面数小于前面的数，交换位置，每一趟排序，都将最大数升到最后面

/**
	 * @author sherlock
	 * 冒泡排序
	 * 一直比较的都是相邻的两个数，把大的冒泡到后边，而不是第一个数一直和后边所有的数都比较一次
	 * @param arr
	 */
	public static void bubbleSort(int[] arr){
		int count = 0;
		for(int i = 0;i<arr.length;i++){
			boolean b = true;
			for(int j = 1;j<arr.length - i;j++){
				if(arr[j-1]>arr[j]){
					int temp = arr[j-1];
					arr[j-1] = arr[j];
					arr[j] = temp;
					b = false;
					
				}
				count ++;
			}
			if(b == true){
				break;
			}
		}
		System.out.println(count);
	}

未完待续。。。。