黑马程序员技术交流社区
标题: 一些必会的基础算法题 [打印本页]
作者: 逆风TO 时间: 2020-3-31 10:41
标题: 一些必会的基础算法题
简单选择排序：
[JavaScript] 纯文本查看 复制代码
public class EasySelectSort {
public static void main(String[] args) {
int arr[]={1,4,6,8,2,5,3,7,9};
System.out.println("数组排序前顺序：");
for (int n:arr){
System.out.print(n+" ");
}
//简单选择排序
selectSort(arr);
System.out.println("\n数组排序后顺序：");
for (int n :arr){
System.out.print(n+" ");
}
}
//简单选择排序
private static void selectSort(int[] arr){
int position = 0;//无序序列中的第一个位置
//外层循环确定有序区
for (int i=0;i<arr.length;i++){ //数组下标从0开始
position = i;
int temp = arr; //把序列中第一个位置暂时作为最小记录
//内层循环确定无序区
for (int j=i+1;j<arr.length;j++){//在无序区查找最小记录
if (arr[j]<temp){ //若最小记录不在最终位置时则交换位置
temp = arr[j];
position = j;//此时无序序列中第一个位置
}
}
//最小记录在最终位置时
arr[position] = arr;
arr=temp;
}
}
}
直接插入排序：
[JavaScript] 纯文本查看 复制代码
public class InsertSort {
public static void main(String[] args) {
int arr[] ={1,4,6,8,2,5,3,7,9};
System.out.println("数组排序前顺序：");
for (int n:arr){
System.out.print(n+"");
}
//直接插入排序
insertSort(arr);
System.out.println("\n数组排序后顺序：");
for (int n:arr){
System.out.print(n+" ");
}
}
//直接插入排序
public static void insertSort(int[] arr){
//外层循环确定待比较数值
for (int i=1;i<arr.length;i++){//必须i=1，因为开始从第二个数与第一个数进行比较
int temp=arr;//待比较数值
int j=i-1;
//内层循环为待比较数值确定其最终位置
for (;j>=0&&arr[j]>temp;j--){ //待比较数值比前一位置小，应插往前插一位
//将大于temp的值整体后移一个单位
arr[j+1]=arr[j];
}
arr[j+1]=temp;//待比较数值比前一位置大，最终位置无误
}
}
}
堆排序：
[JavaScript] 纯文本查看 复制代码
public class HeapSort {
public static void main(String[] args) {
[JavaScript] 纯文本查看 复制代码
int arr[] = {1,4,6,8,2,5,3,7,9};
System.out.println("数组排序前顺序：");
for(int n : arr){
System.out.print(n+" ");
}
//堆排序
heapSort(arr);
System.out.println("\n数组排序后顺序：");
for(int n : arr){
System.out.print(n+" ");
}
}
//堆排序
private static void heapSort(int []arr){
//1.构建大根堆
for (int i=arr.length/2-1;i>=0;i--){//第一个非叶子结点下标i=arr.length/2-1
//从第一个非叶子结点从下至上，从右至左调整结构
adjustHeap(arr,i,arr.length);
}
//2.交换堆顶元素与末尾元素+调整堆结构
for (int j=arr.length-1;j>0;j--){//堆末尾元素的下标j=arr.length-1,不能为0，因为它不能是堆顶元素
//将堆顶元素与末尾元素进行交换
int temp=arr[0];
arr[0]=arr[j];
arr[j]=temp;
//重新对堆进行调整
adjustHeap(arr,0,j);
}
}
//调整大根堆（仅是调整过程，建立在大根堆已构建的基础上）
// arr: 要排序的序列(数组)
// i: 第一个非叶子结点下标
// n: 剩余序列的长度(需要调整的结点个数)
private static void adjustHeap(int []arr,int i,int n){
int temp = arr;//先取出第一个非叶子结点(根节点)
for(int k=i*2+1;k<n;k=k*2+1){//从i结点的左子结点开始，也就是2i+1处开始
if(k+1<n && arr[k]<arr[k+1]){//如果左子结点小于右子结点，k指向右子结点(k+1,即2i+2)
k++;
}
if(arr[k] > temp){//如果子节点大于父节点，将子节点值赋给父节点（不用进行交换）
arr = arr[k];
i = k;
}else{
break;
}
}
arr = temp;//将temp值放到最终的位置
}
希尔排序：
[Java] 纯文本查看 复制代码
public class SheelSort {
public static void main(String[] args) {
int arr[]={1,4,6,8,2,5,3,7,9};
System.out.println("数组排序前顺序：");
for (int n:arr){
System.out.println(n);
}
//希尔排序
SheelSort(arr);
System.out.println("\n数组排序后顺序：");
for (int n:arr){
System.out.println(n);
}
}
//希尔排序
private static void SheelSort(int[] arr){
int i,j,temp,gap=1,len=arr.length;
while (gap<len/3){
gap=gap*3+1;
}
for (;gap>0;gap/=3){
for (i=gap;i<len;i++){
temp = arr;
for (j=i-gap;j>=0&&arr[j]>temp;j-=gap){
arr[j+gap]=arr[j];
}
arr[j+gap]=temp;
}
}
}
}
归并排序：
public class MergeSort {
public static void main(String[] args) {
int arr[] = {1,4,6,8,2,5,3,7,9};
System.out.println("数组排序前顺序：");
for(int n : arr){
System.out.print(n+" ");
}
//归并排序
int lower = 0;
int upper = arr.length-1;
mergeSort(arr, lower, upper);
System.out.println("\n数组排序后顺序：");
for(int n : arr){
System.out.print(n+" ");
}
}
//归并排序
private static void mergeSort(int[] arr, int lower, int upper) {
if (lower < upper) {
//找出中间索引
int middle = (lower + upper)/2;
//对左边数组进行递归
mergeSort(arr, lower, middle); //注意：此处和快速排序不一样，middle不需要减1，组成一个完整序列的下标
//对右边数组进行递归
mergeSort(arr, middle+1, upper);
//合并
merge(arr, lower, middle, upper);
}
}
//归并
private static void merge(int[] arr, int lower, int middle, int upper) {
int[] tempArr = new int[arr.length]; //建立一个中间数组
int mid = middle + 1; // 第二个子序列的第一个下标
int third = lower; //third记录中间数组的索引
int temp = lower;
while (lower <= middle && mid <= upper) {
//从两个数组中取出最小的放入中间数组
if (arr[lower] <= arr[mid]) {
tempArr[third++] = arr[lower++];
} else {
tempArr[third++] = arr[mid++];
}
}
//剩余部分依次放入中间数组
while (mid <= upper) {
tempArr[third++] = arr[mid++];
}
while (lower <= middle) {
tempArr[third++] = arr[lower++];
}
//将中间数组中的内容复制回原数组
while (temp <= upper) {
arr[temp] = tempArr[temp++];
}
}
}
基数排序：
[Java] 纯文本查看 复制代码
public class JiShuSort {
public static void main(String[] args) {
int arr[] = {1,4,6,8,2,5,3,7,9};
System.out.println("数组排序前顺序：");
for(int n : arr){
System.out.print(n+"");
}
//基数排序
radixSort(arr);
System.out.println("\n数组排序后顺序：");
for (int n:arr){
System.out.print(n+"");
}
}
//基数排序
private static void radixSort(int[] arr){
//首先确定排序的趟数
int max=arr[0];
for (int i=1;i<arr.length;i++){
if (arr>max){
max=arr;
}
}
int time=0;
//判断位数
while (max>0){
max/=10;
time++;
}
//建立10个List集合
List<List<Integer>> list=new ArrayList<List<Integer>>();
for (int i=0;i<10;i++){
List<Integer> list1 = new ArrayList<Integer>();
list.add(list1);
}
//进行time次分配和收集
for (int i=0;i<time;i++){
//分配数组元素
for (int n:arr){
//得到数字的第time+1位数
int x=n%(int)Math.pow(10,i+1)/(int)Math.pow(10,i);
List<Integer> list2=list.get(x);
list2.add(n);
list.set(x,list2);
}
int count =0;//元素计数器
//收集队列元素
for (int k=0;k<10;k++){
while(list.get(k).size()>0){
List<Integer> list3=list.get(k);
arr[count] = list3.get(0);
list3.remove(0);
count++;
}
}
}
}
}
转自CSDN
作者: 1467584 时间: 2020-4-7 10:21
66666666666666666666666666
作者: kdhdjdj 时间: 2020-4-7 10:21
6666666666666666666666666666666666666666666666
作者: 1467584 时间: 2020-4-7 10:21
6666666666666666666666666666
作者: 王锦 时间: 2020-4-7 10:27
作者: 你不爱我 时间: 2020-4-7 10:42
厉害了
作者: 逆风TO 时间: 2020-4-7 10:56
感谢分享 棒棒哒
作者: sdjadyhm 时间: 2020-4-7 10:56
666666666666666 
作者: 我是小圆圆 时间: 2020-4-7 11:01
可以的，奥利给！！！
作者: hongping 时间: 2020-4-7 11:10
感谢分享 棒棒哒
作者: hongping 时间: 2020-4-7 11:12
感谢分享 棒棒哒
作者: daoqin 时间: 2020-4-7 11:27
可以的，奥利给！！！
作者: 哦嗨呦 时间: 2020-4-7 11:30
好人一生平安
作者: Emmmmm~ 时间: 2020-4-7 11:36
键盘敲烂，月薪过万
作者: 孙丽 时间: 2020-4-7 11:51
66666666666666666666666
作者: manyihang 时间: 2020-4-7 14:47
666666666666
作者: jsnoob 时间: 2020-4-7 14:54
加油加油加油！！！
作者: 章鱼顶呱呱 时间: 2020-4-8 09:53
6666666666666666666
作者: 耙丫丫 时间: 2020-4-9 08:46
6666666666666666666666666
作者: lvxinvip 时间: 2020-4-9 09:21
作者: longyu3 时间: 2020-4-9 09:50
棒棒哒 加油 完美入行
作者: duanshaobo 时间: 2020-4-9 09:59
在这春暖花开的季节
作者: mydorling11 时间: 2020-4-9 10:01
666666666666666666666666666666
作者: 半个程序员 时间: 2020-4-9 14:03
可以的，奥利给！！！
作者: 举个栗子 时间: 2020-4-9 14:41
666666666666666666666666666666
作者: json0314 时间: 2020-4-9 14:50
加油哦.加油哦!
作者: 123木头人555 时间: 2020-4-9 15:19
6666666666666666666666666666
作者: 小公举 时间: 2020-4-9 15:28
6666666666666666666
作者: yujq 时间: 2020-4-9 18:22
66666666666666666
作者: 零度☆黎明 时间: 2020-4-9 23:14
66666666666666666666666666666666666666666666666666
作者: zplxwl 时间: 2020-4-10 00:31
666666666666666666666666
作者: 大智叔叔 时间: 2020-4-10 09:28
6666666666666666666666666
作者: 九月丫 时间: 2020-4-10 09:35
6666666666666666666666666666666666666666666666666
作者: lzq123 时间: 2020-4-10 09:36
666666666666666666666666666666666
作者: lzq123 时间: 2020-4-10 09:37
66666666666666666666666666666666666
作者: 我爱我1022 时间: 2020-4-10 09:38
作者: 我爱我1022 时间: 2020-4-10 09:38
作者: lzq123 时间: 2020-4-10 09:41
66666666666666666666666666666
作者: 竹竹竹竹 时间: 2020-4-10 10:05
666666666666666666666666666666666
作者: 影@子~ 时间: 2020-4-10 10:06
作者: 王微 时间: 2020-4-10 10:16
666666666666666666666
作者: zhaosongzhi 时间: 2020-4-10 10:41
6666666666666666
作者: 霍尔 时间: 2020-4-10 10:54
66666666666666666666
作者: hello！！！ 时间: 2020-4-10 11:07
作者: 黑马程序员啊 时间: 2020-4-10 12:58
6666666666666666666666666666666
作者: 雨落轻舟 时间: 2020-4-10 18:35
6666666666666666666666666666666666666666666666666666666666666666
作者: 素问 时间: 2020-4-12 22:13
谢谢分享，加油~~~~！！！！
| 欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/) |
黑马程序员IT技术论坛 X3.2 |