java零基础 IntelliJ IDEA教程 摩尔投票法 WorldCloud centos7 installation layer jar devise textview vue路由 传智播客python float占几个字节 matlab四舍五入 html好看的字体 matlab中如何定义函数 vue与html5 flutter项目案例 python断言assert实例 python加法 python环境设置 python命令行参数 javaqueue java学习手册 java连数据库 java中的正则表达式 java接口的实例 python源码 跳一跳脚本 kms神龙 视频字幕提取器 战地联盟辅助 矩阵分析与应用 快打旋风3出招表 skycc组合营销软件 流程图工具 dnf瞎子传说套选择 备份数据的软件 早早省 ios12录屏
当前位置: 首页 > 学习教程  > 编程语言

排序算法(1)

2020/10/8 19:54:22 文章标签:

冒泡排序 private static void bubbleSort(int[] arr) {if (arr null || arr.length < 2) {return;}for (int end arr.length - 1; end > 0; end--) {for (int i 0; i < end; i) {if(arr[i] > arr[i 1]) {swap(arr, i, i 1);}}} }选择排序 private static v…

冒泡排序

private static void bubbleSort(int[] arr) {
	if (arr == null || arr.length < 2) {
		return;
	}
	for (int end = arr.length - 1; end > 0; end--) {
		for (int i = 0; i < end; i++) {
			if(arr[i] > arr[i + 1]) {
				swap(arr, i, i + 1);
			}
		}
	}
}

选择排序

private static void selectSort(int[] arr) {
	if (arr == null || arr.length < 2) {
		return;
	}
	for (int i = 0; i < arr.length - 1; i++) {
		int minIndex = i;
		for (int j = i + 1; j < arr.length; j++) {
			minIndex = arr[j] > arr[minIndex] ? minIndex : j;
		}
		swap(arr, i, minIndex);
	}
}

插入排序

private static void insertionSort(int[] arr) {
	if (arr == null || arr.length < 2) {
		return;
	}
	for (int i = 1; i < arr.length; i++) {
		int j = i - 1;
		while (j >= 0 && arr[j] > arr[j + 1]) {
			swap(arr, j, j + 1);
			j--;
		}
	}
}

归并排序

private static void mergeSort(int[] arr) {
	if (arr == null || arr.length < 2) {
            return;
    }
    mergeSort(arr, 0, arr.length - 1);
}
private static void mergeSort(int[] arr, int l, int r) {
	if (l == r) {
		return;
	}
	int mid = l + (r - l) / 2;
	mergeSort(arr, l, mid);
	mergeSort(arr, mid + 1, r);
	merge(arr, l, mid, r);
}
private static void merge(int[] arr, int l, int mid, int r) {
	int[] help = new int[r - l + 1];
	int p1 = l, p2 = mid + 1;
	int i = 0;
	while (p1 <= mid && p2 <= r) {
		help[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
	}
	while (p1 <= mid) {
		help[i++] = arr[p1++];
	}
	while (p2 <= r) {
		help[i++] = arr[p2++];
	}
	for (i= 0; i < help.length; i++) {
		arr[l + i] = help[i];
	}
}

荷兰国旗

public class NetherlandsFlag {
    public static void main(String[] args) {
        int[] arr = {2,3,5,3,3,6,9,8,4,5,5,5};
        int[] sameArr = partition(arr, 0, arr.length - 1, 5);
        System.out.println(Arrays.toString(sameArr));
        System.out.println(Arrays.toString(arr));
    }

    private static int[] partition(int[] arr, int L, int R, int num) {
    	int less = L - 1;
    	int more = R + 1;
    	int cur = L;
    	while (cur < more) {
    		if (arr[cur] < num) {
				swap(arr, ++less, cur++);
			} else if (arr[cur] > num) {
				swap(arr, --more, cur);
			} else {
				cur++;
			}
    	}
    	return new int[]{less + 1, more - 1};
    }

    private static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
}

快速排序

public static void main(String[] args) {
	int[] arr = {4,5,2,2,6,9,10};
	quickSort(arr);
	System.out.println(Arrays.toString(arr));
}
private static void quickSort(int[] arr) {
	quickSort(arr, 0, arr.length - 1);
}
private static void quickSort(int[] arr, int left, int right) {
	if (left < right) {
		int pos = partition(arr, left, right);
		quickSort(arr, left, pos - 1);
		quickSort(arr, pos + 1, right);
	}
}
private static int partition(int[] arr, int left, int right) {
	int pivot = arr[left];
	int i = left, j = right;
	while (i < j) {
		// 从右向左找到第一个小于pivot的数
		while (i < j && arr[j] >= pivot) {
			j--;
		}
		if (i < j) {
			arr[i++] = arr[j];
		}
		while (i < j && arr[i] < pivot) {
			i++;
		}
		if (i < j) {
			arr[j--] = arr[i];
		}
	}
	arr[i] = pivot;
	return i;
}
public static void main(String[] args) {
	int[] arr = {4,5,2,2,6,9,10};
	quickSort(arr);
	System.out.println(Arrays.toString(arr));
}
private static void quickSort(int[] arr) {
	if (arr == null || arr.length < 2) {
		return;
	} 
	quickSort(arr, 0, arr.length - 1);
}
private static void quickSort(int[] arr, int l, int r) {
	if (l < r) {
		swap(arr, l + (int) Math.random() * (r - l + 1), r);
		int[] pos = partition(arr, l, r);
		quickSort(arr, l, pos[0] - 1);
		quickSort(arr, pos[1] + 1, r);
	}
}
private static int[] partition(int[] arr, int l, int r) {
	int less = l - 1;
	int more = r + 1;
	while (l < more) {
		if (arr[l] < arr[r]) {
			swap(arr, ++less, l++);
		} else if (arr[l] > arr[r]) {
			swap(arr, --more, l);
		} else {
			l++;
		}
	}
	return new int[]{less + 1, more - 1};
}
private static void swap(int[] arr, int i, int j) {
	int tmp = arr[i];
	arr[i] = arr[j];
	arr[j] = tmp;
}

堆排序

public static void main(String[] args) {
	int[] arr = {5,2,1,4,3};
	heapSort(arr);
	System.out.println(Arrays.toString(arr));
}
private static void heapSort(int[] arr) {
	int size = arr.length;
	if (arr == null || size < 2) {
		return;
	}
	// 构建大根堆
	for (int i = 0; i < size; i++) {
		heapInsert(arr, i);
	}
	// 调整大根堆
	while (size > 1) {
		swap(arr, 0, size - 1);
		size--;
		heapify(arr, 0, size);
	}
}
private static void heapInsert(int[] arr, int index) {
	while (arr[index] > arr[(index - 1) / 2]) {
		swap(arr, index, (index - 1) / 2);
		index = (index - 1) / 2;
	}
}
private static void heapify(int[] arr, int index, int size) {
	int left = 2 * index + 1;
	while (left < size) {
		int largestIndex = 0;
		if (left + 1 < size && arr[left + 1] > arr[left]) {
			largestIndex = left + 1;
		} else {
			largestIndex = left;
		}
		largestIndex = arr[index] > arr[largestIndex] ? index : largestIndex;
		if (index == largestIndex) {
			break;
		}
		swap(arr, index, largestIndex);
		index = largestIndex;
		left = 2 * index + 1;
	}
}
private static void swap(int[] arr, int i, int j) {
	int tmp = arr[i];
	arr[i] = arr[j];
	arr[j] = tmp;
}

本文链接: http://www.dtmao.cc/news_show_250176.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?