经典排序算法
排序算法
冒泡排序
原始冒泡排序代码实现
public static void bubbleSort(int array[]) {
for(int i = 0;i < array.length - 1;i++) {
for(int j = 0;j < array.length - 1 - i;j++){
int temp = 0;
if(array[j] > array[j+1]){
temp = array[j];
array[j] = array[j+1];
array[j+1] = temp;
}
}
}
}
优化后的冒泡排序
public static void optBubbleSort(int array[]) {
//有序标记，每一轮的初始值为true
boolean flag = true;
for(int i = 0;i < array.length - 1;i++) {
flag = true;
for(int j = 0;j < array.length - 1 - i;j++){
int temp = 0;
if(array[j] > array[j+1]){
temp = array[j];
array[j] = array[j+1];
array[j+1] = temp;
//有元素交换，说明不是有序的，标记置为false
flag = false;
}
}
if(flag){
break;
}
}
}
优化后的冒泡排序(数列有序区的界定)
public static void BubbleSort2(int array[]) {
//记录最后一次交换的位置
int lastExchange = 0;
//记录有序区的位置
int sortBorder = array.length - 1;
boolean flag = true;
for(int i = 0;i < array.length - 1;i++) {
flag = true;
for(int j = 0;j < sortBorder;j++){
int temp = 0;
if(array[j] > array[j+1]){
temp = array[j];
array[j] = array[j+1];
array[j+1] = temp;
lastExchange = j;
flag = false;
}
}
//得到有序区的位置
sortBorder = lastExchange;
if(flag){
break;
}
}
}
快速排序
使用分治法的思想，原数列在每一轮都被拆分成两部分，每一部分在下一轮又分别被拆分成两部分，直到不可再分为止。
基准元素的选择
- 最简单的方式是选择数列的第1个元素。
- 随机选择一个元素作为基准元素，并且让基准元素和数列首元素交换位置。
元素的交换
-
双边循环法
-
选定基准元素pivot，并且设置两个指针left和right，指向数列的最左和最右两个元素。
-
从right指针开始，如果right指向的元素大于或等于pivot，则指针向左移动；如果小于pivot，则right指针停止移动，切换到left指针。
-
left指针行动，如果left指针所指向的元素小于或等于pivot，则指针向右移动；如果大于pivot，则left指针停止移动。
-
left和right指针所指向的元素进行交换。
-
回到步骤3，进入下一轮循环，直到left == right
-
-
单边循环法
- 首先选定基准元素pivot。同时，设置一个mark指针指向数列起始位置，这个mark指针代表小于基准元素的区域边界。
- 从基准元素的下一个位置开始遍历数组。
- 遍历到的元素小于基准元素，则需要做两件事：第一，把mark指针右移1位，因为小于pivot的区域边界增大了1；第二，让最新遍历到的元素和mark指针所在位置的元素交换位置，因为最新遍历的元素归属于小于pivot的区域。
- 一直循环遍历，直到遍历完所有元素。
快速排序（递归）
pivotIndex = partition(arr, startIndex, endIndex);quickSort(arr, startIndex, pivotIndex-1);quickSort(arr, pivotIndex+1, endIndex);
快速排序（非递归）
- 引入了一个存储Map类型元素的栈，用于存储每一次交换时的起始下标和结束下标。
- 每一次循环，都会让栈顶元素出栈，通过partition方法进行分治，获得基准元素下标。
- 按照基准元素的位置分成左右两部分，左右两部分再分别入栈。
- 当栈为空时，说明排序已经完毕，退出循环。
快速排序代码实现
package Algorithm;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Stack;
public class QuickSort {
/** * 快速排序（递归实现） * @param arr 待排序的数组 * @param startIndex 开始下标 * @param endIndex 结束下标 */
public static void quickSort(int[] arr,int startIndex, int endIndex) {
//递归结束条件：startIndex大于等于endIndex
if(startIndex >= endIndex)
return;
int pivotIndex = onePartition(arr, startIndex, endIndex);
//根据基准元素，分成两部分进行递归
quickSort(arr, startIndex, pivotIndex-1);
quickSort(arr, pivotIndex+1, endIndex);
}
/** * 快速排序（非递归实现） * @param arr 待排序的数组 * @param startIndex 开始下标 * @param endIndex 结束下标 */
public static void noRecurQuickSort(int[] arr,int startIndex, int endIndex) {
Stack<Map<String, Integer>> quickSort =
new Stack<>();
Map rootParam = new HashMap();
rootParam.put("startIndex", startIndex);
rootParam.put("endIndex", endIndex);
quickSort.push(rootParam);
//循环结束条件：栈为空
while (!quickSort.isEmpty()) {
//栈顶元素出栈，得到起止下标
Map<String, Integer> param = quickSort.pop();
//得到基准元素
int pivotIndex = onePartition(arr, param.get("startIndex"), param.get("endIndex"));
//根据基准元素分为两部分，把每一部分的起止下标入栈
if(param.get("startIndex") < pivotIndex - 1) {
Map<String, Integer> leftParam = new HashMap<>();
leftParam.put("startIndex", param.get("startIndex"));
leftParam.put("endIndex", pivotIndex - 1);
quickSort.push(leftParam);
}
if(pivotIndex + 1 < param.get("endIndex")) {
Map<String, Integer> rightParam = new HashMap<>();
rightParam.put("startIndex", pivotIndex + 1);
rightParam.put("endIndex", param.get("endIndex"));
quickSort.push(rightParam);
}
}
}
/** * 分治（双边循环法） * @param arr 待交换的数组 * @param startIndex 起始下标 * @param endIndex 结束下标 * @return 中间元素下标 */
public static int partition(int[] arr, int startIndex, int endIndex) {
int pivot = arr[startIndex];
int left = startIndex;
int right = endIndex;
while (left != right) {
//控制left指针右移
while (left < left && arr[right] > pivot) {
right--;
}
//控制right指针左移
while (left < right && arr[left] <= pivot) {
left++;
}
//交换left指针和right指针指向的元素
if(left < right) {
int temp = arr[left];
arr[left] = arr[right];
arr[right] = temp;
}
}
//交换基准元素
arr[startIndex] = arr[left];
arr[left] = pivot;
return left;
}
/** * 分治（单边循环法） * @param arr 待交换的数组 * @param startIndex 起始下标 * @param endIndex 结束下标 * @return 基准元素下标 */
public static int onePartition(int[] arr, int startIndex, int endIndex) {
int pivot = arr[startIndex];
int mark = startIndex;
int temp = 0;
for(int i = startIndex + 1;i <= endIndex;i++) {
if(arr[i] < pivot) {
mark++;
temp = arr[mark];
arr[mark] = arr[i];
arr[i] = temp;
}
}
arr[startIndex] = arr[mark];
arr[mark] = pivot;
return mark;
}
public static void main(String[] args) {
int[] array = {5,8,6,3,9,2,1,7};
System.out.println(Arrays.toString(array));
noRecurQuickSort(array, 0, array.length-1);
System.out.println(Arrays.toString(array));
}
}
堆排序
算法步骤
- 把无序数组构建成二叉堆。需要从小到大排序，则构建成最大堆；需要从大到小排序，则构建成最小堆。
- 循环删除堆顶元素，替换到二叉堆的末尾，堆的有效长度减一，调整堆产生新的堆顶
堆排序的代码实现
public static void heapSort(int[] array) {
int head = 0;
BinaryHeap.buildHeap(array);
for(int i = array.length - 1;i > 0;i--) {
head = array[0];
array[0] = array[i];
array[i] = head;
//堆顶下沉
BinaryHeap.downAdjust(array, 0, i);
}
}
Momenta公司福利 293人发布
查看12道真题和解析