排序算法的两个原则：
1.输出结果为递增或者递减。
2.输出结果为原输入结果的排列或者重组。
平均时间复杂度为O(n^2)的排序算法有三种：
冒泡排序，插入排序，选择排序。
一。冒泡排序：
即谁冒泡泡冒得快，上升的就快。
1 /*冒泡排序 复杂度O(n^2)
2 * 1.比较相邻的元素。如果第一个比第二个大，就交换他们两个。
3 2.对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
4 3.针对所有的元素重复以上的步骤，除了最后一个。
5 4.持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
6 */
7 public int[] BubblingSort(int[] arr)
8 {
9 int temp = 0;
10 boolean unsort = true;
11
12 while(unsort)
13 {
14 for(int i=0;i<arr.length;i++)
15 {
16 if(arr[i]>arr[i+1])
17 {
18 temp = arr[i];
19 arr[i] = arr[i+1];
20 arr[i+1] = temp;
21 unsort = true;
22 }
23 }
24 }
25 return arr;
26 }
冒泡排序平均时间复杂度为O(n^2)。
二。插入排序
工作原理是通过构建有序序列，对于未排序的数据，在已排序的序列中从后向前扫描，找到相应位置并插入。
主要有两个动作：操作和交换。
1 /*插入排序 默认第一个元素是已被排序
2 * 取出下一个元素 在已排序的元素中进行比较
3 * 如果已排序的元素大于该元素 则将该元素移动到下一位置
4 * 直到找到小于或等于的该元素的位置
5 * 将该元素插入到该位置
6 * 如果比较操作的代价大于交换操作的话 就要考虑用二分查找法
7 * 最差复杂度O(N^2) 最优时间复杂度O(N) 平均时间复杂度O(N^2) 空间复杂度O(N)
8 * 和冒泡排序是一个级别
9 */
10 public void insertSort(int[] data)
11 {
12 int temp = 0;
13 for(int i=1;i<data.length;i++)
14 {
15 for(int j=i;(j>0)&&(data[j]<data[j-1]);j--)
16 {
17 temp = data[j-1];
18 data[j-1] = data[j];
19 data[j] = temp;
20 }
21 }
22 }
三，选择排序
在未排序序列中找到最小元素，存放在排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小最小元素，然后放到排序序列的末尾。以此类推，知道所有元素均排序完毕。
1 /*选择排序：首先在未排序的元素中找到最小的元素 放在排序序列的起始位置
2 * 然后在从生下的序列元素中继续找到最小元素，然后放在已排序序列的末尾
3 * 复杂度O(N^2)*/
4 public void selectionSort(int[] array)
5 {
6 int i,j;
7 int temp;
8 for(i=0;i<array.length-1;i++)
9 {
10 int min = i;
11 for(j=i+1;j<array.length;j++)
12 {
13 if(array[min] > array[j])
14 {
15 min=j;
16 }
17 }
18
19 temp = array[min];
20 array[min] = array[i];
21 array[i] = temp;
22
23 }
24 }