经典排序算法
十大排序算法
1、冒泡排序 public class BubbleSort implements IArraySort { @Override public int [] sort(int [] sourceArray) throws Exception { int [] arr = Arrays.copyOf(sourceArray, sourceArray.length); for (int i = 1 ; i < arr.length; i++) { boolean flag = true ; for (int j = 0 ; j < arr.length - i; j++) { if (arr[j] > arr[j + 1 ]) { int tmp = arr[j]; arr[j] = arr[j + 1 ]; arr[j + 1 ] = tmp; flag = false ; } } if (flag) { break ; } } return arr; } }
2、选择排序 public class SelectionSort implements IArraySort { @Override public int [] sort(int [] sourceArray) throws Exception { int [] arr = Arrays.copyOf(sourceArray, sourceArray.length); for (int i = 0 ; i < arr.length - 1 ; i++) { int min = i; for (int j = i + 1 ; j < arr.length; j++) { if (arr[j] < arr[min]) { min = j; } } if (i != min) { int tmp = arr[i]; arr[i] = arr[min]; arr[min] = tmp; } } return arr; } }
3、插入排序
只要打过扑克牌的人都应该能够秒懂。
public class InsertSort implements IArraySort { @Override public int [] sort(int [] sourceArray) throws Exception { int [] arr = Arrays.copyOf(sourceArray, sourceArray.length); for (int i = 1 ; i < arr.length; i++) { int tmp = arr[i]; int j = i; while (j > 0 && tmp < arr[j - 1 ]) { arr[j] = arr[j - 1 ]; j--; } if (j != i) { arr[j] = tmp; } } return arr; } }
4、希尔排序
插入排序的一种更高效的改进版本。但希尔排序是非稳定排序算法。
public class ShellSort implements IArraySort { @Override public int [] sort(int [] sourceArray) throws Exception { int [] arr = Arrays.copyOf(sourceArray, sourceArray.length); int gap = 1 ; while (gap < arr.length) { gap = gap * 3 + 1 ; } while (gap > 0 ) { for (int i = gap; i < arr.length; i++) { int tmp = arr[i]; int j = i - gap; while (j >= 0 && arr[j] > tmp) { arr[j + gap] = arr[j]; j -= gap; } arr[j + gap] = tmp; } gap = (int ) Math.floor(gap / 3 ); } return arr; } }
5、归并排序
归并排序(Merge sort)是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。
图解归并排序
public class MergeSort implements IArraySort { @Override public int [] sort(int [] sourceArray) throws Exception { int [] arr = Arrays.copyOf(sourceArray, sourceArray.length); if (arr.length < 2 ) { return arr; } int middle = (int ) Math.floor(arr.length / 2 ); int [] left = Arrays.copyOfRange(arr, 0 , middle); int [] right = Arrays.copyOfRange(arr, middle, arr.length); return merge(sort(left), sort(right)); } protected int [] merge(int [] left, int [] right) { int [] result = new int [left.length + right.length]; int i = 0 ; while (left.length > 0 && right.length > 0 ) { if (left[0 ] <= right[0 ]) { result[i++] = left[0 ]; left = Arrays.copyOfRange(left, 1 , left.length); } else { result[i++] = right[0 ]; right = Arrays.copyOfRange(right, 1 , right.length); } } while (left.length > 0 ) { result[i++] = left[0 ]; left = Arrays.copyOfRange(left, 1 , left.length); } while (right.length > 0 ) { result[i++] = right[0 ]; right = Arrays.copyOfRange(right, 1 , right.length); } return result; } }
6、快速排序
快速排序又是一种分而治之思想在排序算法上的典型应用。本质上来看,快速排序应该算是在冒泡排序基础上的递归分治法。
实例 public class QuickSort implements IArraySort { @Override public int [] sort(int [] sourceArray) throws Exception { int [] arr = Arrays.copyOf(sourceArray, sourceArray.length); return quickSort(arr, 0 , arr.length - 1 ); } private int [] quickSort(int [] arr, int left, int right) { if (left < right) { int partitionIndex = partition(arr, left, right); quickSort(arr, left, partitionIndex - 1 ); quickSort(arr, partitionIndex + 1 , right); } return arr; } private int partition (int [] arr, int left, int right) { int pivot = left; int index = pivot + 1 ; for (int i = index; i <= right; i++) { if (arr[i] < arr[pivot]) { swap(arr, i, index); index++; } } swap(arr, pivot, index - 1 ); return index - 1 ; } private void swap (int [] arr, int i, int j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } }