Open wangzhenhui1991 opened 7 years ago
助记码
i∈[0,N-1) //循环N-1遍 j∈[0,N-1-i) //每遍循环要处理的无序部分 swap(j,j+1) //两两排序(升序/降序)
public class BubbleSort { public static void bubble_sort(int[] arr) { int i, j, temp, len = arr.length; for (i = 0; i < len - 1; i++) for (j = 0; j < len - 1 - i; j++) if (arr[j] > arr[j + 1]) { temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; } } public static void main(String[] args) { int[] number = {95,45,15,78,84,51,24,12}; int temp = 0; bubble_sort(number); for(int i = 0; i < number.length; i++) System.out.print(number[i] + " "); System.out.println(); } }
快速排序使用分治法(Divide and conquer)策略来把一个序列(list)分为两个子序列(sub-lists)。 步骤为:
虽然一直递归下去,但是这个算法总会结束,因为在每次的迭代(iteration)中,它至少会把一个元素摆到它最后的位置去。
class quick_sort { int[] arr; public void sort(int[] arrin) { arr = arrin; quick_sort_recursive(0, arr.length - 1); } public void quick_sort_recursive(int start, int end) { if (start >= end) return; int pivotpos=partition(start,end); quick_sort_recursive(start, left - 1); quick_sort_recursive(left + 1, end); } private int partition(int low,int high){ int mid = arr[end];//以最后一个结点作为基准 int left = low, right = high - 1; while (left < right) { while (arr[left] < mid && left < right) left++; while (arr[right] >= mid && left < right) right--; swap(left, right); } if (arr[left] >= arr[end]) swap(left, end); else left++; return left; } private void swap(int x, int y) { int temp = arr[x]; arr[x] = arr[y]; arr[y] = temp; } }
快排平均时间复杂度是 O(nlogn) 从上面的过程中可以看出,我们最理想情况下希望选出的 pivot 直接就是中心点。那么有时候满足不了,比如说:
O(nlogn)
这样会导致分出来的左右两部分不均匀,就像一个倾斜了的二叉树一样。
快速排序的优化
交换排序--冒泡排序
助记码
交换排序--快速排序
快速排序使用分治法(Divide and conquer)策略来把一个序列(list)分为两个子序列(sub-lists)。 步骤为:
虽然一直递归下去,但是这个算法总会结束,因为在每次的迭代(iteration)中,它至少会把一个元素摆到它最后的位置去。
算法复杂度
算法缺点
快排平均时间复杂度是
O(nlogn)
从上面的过程中可以看出,我们最理想情况下希望选出的 pivot 直接就是中心点。那么有时候满足不了,比如说:这样会导致分出来的左右两部分不均匀,就像一个倾斜了的二叉树一样。
参考
快速排序的优化