1、冒泡
时间复杂度O(n^2)
算法步骤：
1）第一轮比较相邻两个元素将大的放在右侧，一轮结束后最大的值在最右侧
2）第二轮继续比较相邻两个元素将大的放在右侧，第二轮结束后次大的值在最有侧第二个
3）如此循环，直到没有数字需要比较
优化：
加一个标记flag，当某一轮无发生数据交换时即排序完成
1 /** 2 * 冒泡排序 3 */ 4 public static int[] bubbleSort(int[] source) { 5 6 int[] arr = Arrays.copyOf(source, source.length); 7 8 for (int i = 0; i < arr.length; i++) { 9 10 // 设置一个标志，如果此次没有元素交换，则说明排序完成 11 boolean flag = true; 12 13 for (int j = 1; j < arr.length - i; j++) { 14 if (arr[j] > arr[i]) { 15 swap(arr, i, j); 16 flag = false; 17 } 18 } 19 20 if (flag) { 21 return arr; 22 } 23 } 24 25 return arr; 26 }
2、选择排序
时间复杂度O(n^2)
算法步骤：
1）第一轮找出最小（大）值坐标，将此坐标值和最右侧数值交换
2）第二轮找出剩余中最小（大）值坐标，将此坐标值和最右侧第二个数值交换
3）如此循环，直到只剩1个
1 /** 2 * 选择排序 3 */ 4 public static int[] selectSort(int[] source) { 5 6 int[] arr = Arrays.copyOf(source, source.length); 7 8 for (int i = 0; i < arr.length; i++) { 9 10 int point = i; 11 12 for (int j = 1; j < arr.length - i; j++) { 13 14 if (arr[j] > arr[point]) { 15 point = j; 16 } 17 } 18 19 swap(arr, point, arr.length - i); 20 } 21 22 return arr; 23 }
3、插入排序
时间复杂度O(n^2)
算法步骤：
1）第一个看作是有序序列，第二个到最后一个看作无序序列
2）取出无序序列的第一个，将其插入到有序序列的合适位置（想象下扑克牌插入）
3）如此循环，直到无序序列都排完
1 /** 2 * 插入排序 3 */ 4 public static int[] insertSort(int[] source) { 5 6 int[] arr = Arrays.copyOf(source, source.length); 7 8 for (int i = 0; i < arr.length; i++) { 9 10 int temp = arr[i]; 11 12 int j = i; 13 14 while (j > 0 && temp > arr[j -1]) { 15 arr[j] = arr[j -1]; 16 17 j--; 18 } 19 20 arr[j] = arr[j]; 21 } 22 23 return arr; 24 }
4、快速排序