• 欢迎光临~

数组八大运算

开发技术 开发技术 2022-05-20 次浏览

数组八大运算

1;冒泡排序

2;选择排序

3;直接插入排序

4;希尔排序

5;快速排序

6;归并排序

7;基数排序

8;堆排序

 

一  冒泡排序

原理;数组元素两两比较,交换位置,大元素向后放。那么经过一轮比较后做大的元素会出现在最大索引处

public class Outer {
public static void main(String[] args) {


//定义一个数组
int[] arr = {14, 10, 30, 32, 71, 51, 23, 40, 99};



for (int j = 0; j < arr.length-1; j++) {//循环次数
for (int i = 0; i < arr.length-1-j; i++) {遍历数组
if(arr[i]>arr[i+1]){
//定义一个中间交换量,交换位置
int t = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = t;
}

}

}
二 选择排序

原理;从0索引开始,依次和后面的元素进行比较,小的元素往前放,经过一轮比较后,最小的元素出现在最小索引处

//定义一个数组
int[] arr = {14, 10, 30, 32, 71, 51, 23, 40, 99};


for (int j = 0; j < arr.length-1; j++) {//循环次数

for (int i = 1+j; i < arr.length; i++) {//遍历数组
if (arr[j] > arr[i]) {//排序思路
int t = arr[j];
arr[j] = arr[i];
arr[i] = t;
}

}
}
三 直接插入排序
思路;将一个元素插入到一个长度为m的有序表中,使他仍保持顺序

方法一

public class Outer {
public static void main(String[] args) {


//定义一个数组
int[] arr = {14, 10, 30, 32, 71, 51, 23, 40, 99};

//外层循环定义轮次
for (int i = 1; i < arr.length; i++) {
//里曾循环进行比较插入
int j=i;
while(j>0&&arr[j]<arr[j-1]){
int t =arr[j];
arr[j]=arr[j-1];
arr[j-1]=t;
j--;

}
}
方法二
//定义一个数组
int[] arr = {14, 10, 30, 32, 71, 51, 23, 40, 99};

//外层循环定义轮次
for (int i = 1; i < arr.length; i++) {
//里曾循环进行比较插入

for(int j =i;j>0;j--){
if(arr[j]<arr[j-1]){
int t =arr[j];
arr[j]=arr[j-1];
arr[j-1]=t;

}
}
}
四  希尔排序
又称缩小增量排序

基本思想;先将原表按增量ht分组,每个子文件按照直接插入法排序,
同样下一个增量ht/2将文件在分为子文件,在直接插入法排序。直到ht等于1时整个文件拍好。
关键;选择合适的增量。
插入排序时增量为1的希尔排序。

//第一次增量可以选取数组长度的一半.克鲁特序列更高效。



//定义一个数组
int[] arr = {14, 10, 30, 32, 71, 51, 23, 40, 99};

//克努特序列,希尔排序的最佳增量
int jiange =1;
while(jiange<=arr.length/3){//如果间隔数小于等于数组长度的3/1,克努特序列成立,定义循环
jiange=jiange*3+1;
}

//三重for循环
for (int h = jiange; h >0; h=(h-1)/3) {//间隔循环,定义间隔
for (int i = h; i < arr.length; i++) {//轮次循环,定义循环轮次
for (int j = i; j > (h-1); j-=h) {//比较循环,间隔为h
if(arr[j]<arr[j-h]){//比较方法体
int t =arr[j];
arr[j]=arr[j-1];
arr[j-1]=t;
}

}

}

}


五 快速排序
分治法;比大小,在区分
1;重数组中去出一个数,作为基准数
2;分区;将比这个数大或者等于的数都放在右边小于的放在左边。
3;重复左右区间的分区,直到各个区间只有一个数
public class Demo1 {
public static void main(String[] args) {

//定义一个数组
int[]arr={10,3,5,6,2,0,200,40,50,8};
//调用工具类,进行快速排序,传入起始位置,传入结束位置
Outer.quickSort(arr,0, arr.length-1);
//输出结果
System.out.println(Arrays.toString(arr));

}
}





public class Outer {
//快速排序
public static void quickSort(int[] arr, int start, int end) {
//找出分左右两区的索引位置,然后对左右两区进行递归调用

if (start < end) {
int index = getIndex(arr, start, end);
quickSort(arr, start, index - 1);
quickSort(arr, index + 1, end);
}

}

private static int getIndex(int[] arr, int start, int end) {
int i = start;
int j = end;
int x = arr[i];
while (i<j){

//由后向前找比他小的数,找到后挖出这个数填到前一个坑中
while (i < j && arr[j] >= x) {
j--;
}
if (i < j) {
arr[i] = arr[j];
i++;
}

//由后向前找比他大或者等于的数,找到后挖出这个数填到前一个坑中
while (i < j && arr[i] < x) {
i++;
}
if (i < j) {
arr[j] = arr[i];
j--;
}
}
arr[i] = x;
return i;
}
}
六 数组排序之归并排序
思路;假设初始序列由n个记录,则可以看成n个有序子序列,每一个子序长度为一,然后凉凉归并
得到n/2个长度为2或者一的有序子序列,在两两归并,直到得到一个长度为n的有序序列为止。

       //原始待排数组
//int [] arr={10,30,2,1,0,8,7,5,19,29};

//我们先给一个左右两边时有序的一个数组,先来进行归并操作

int[] arr ={4,5,7,8,1,2,3,6};
//拆分

//归并
guiBing(arr,0,3,arr.length-1);
//
}

private static void guiBing(int[] arr,int startIndex,int centerIndex,int endIndex){
//定义一个临时数组接受数据
int[] tempArr =new int[endIndex-startIndex+1];
//定义左边数组起始索引
int i =startIndex;

//定义右边数组的起始长度
int j =centerIndex+1;
//定义临时数组的起始索引
int index =0;
//比较两边数组元素大小,往临时数组放
while(i<=centerIndex&&j<=endIndex){
if(arr[i]<=arr[j]){
tempArr[index] =arr[i];
i++;
}else {
tempArr[index]=arr[j];
j++;
}
index++;
}
//处理剩余元素
while(i<=centerIndex){
tempArr[index]=arr[i];
i++;
index++;
}
while (j<=endIndex){
tempArr[index] =arr[j];
j++;
index++;
}
System.out.println(Arrays.toString(tempArr));
}
}

七;基数排序
通过分配在收集的方式进行排序

public class Outer {

public static void main(String[] args) {
//基数排序。通过分配在收集的方式进行排序
int[] arr ={2,1,5,21,31,444,23,33,47,10,903,124,987,100};
//确定排序轮次
//获取数组中的最大值
// int max =getMax(arr);

sortArrary(arr);

//输出排序后的数组
// System.out.println(Arrays.toString(arr));

}

private static void sortArrary(int[] arr) {
//定义二维数组,放十个桶。
int[][] tempArr=new int[10][arr.length];
//定义一维数组,统计数组
int[] counts =new int[10];
int max =getMax(arr);
int len = String.valueOf(max).length();
//循环轮次
for (int i = 0,n=1; i < len; i++,n*=10) {
for (int j = 01;j < arr.length; j++ ) {

//获取每个位上的数字
int ys = arr[j]/n%10;
tempArr[ys][counts[ys]++]=arr[j];
}
//取出桶中元素
int index =0;
for (int k = 0; k < counts.length; k++) {
if(counts[k]!=0){
for (int h = 0; h < counts[k]; h++) {
//桶中取出元素放回原数组
arr[index]=tempArr[k][h];
index++;
}
counts[k]=0;//清除上一位
}

}
}
}

private static int getMax(int[] arr) {
int max =arr[0];
for (int i = 1; i < arr.length; i++) {
if(arr[i]>max){
max=arr[i];
}

}
return max;
}
}

八 堆排序
思想;1;将待排序的序列造成一个大顶堆,此时整个序列最大值就是顶堆的根节点
2;将其末尾元素进行交换,此时末尾就是最大值
3;然后将n-1个元素重新构造成一个堆。这样会得到n个元素的次小值
4;如此反复,得到有序序列


public class Outer {

public static void main(String[] args) {
//定义一个数组
int []arr ={1,0,6,7,2,3,4};
//调整成为顶堆的方法
//定义开始调整的位置
int startIndex=(arr.length-1)/2;
//循环开始
for(int i =startIndex;i>=0;i--){
toMaxHeap(arr,arr.length,i);
}
System.out.println(Arrays.toString(arr));
}
private static void toMaxHeap(int[] arr,int size,int index){
//获取左右字节
int leftNodeIndex=index*2+1;
int rightNodeIndex=index*2+2;
//查找最大节点
int maxIndex=index;
if(arr[leftNodeIndex]>arr[maxIndex]&&leftNodeIndex<size){
maxIndex=leftNodeIndex;
}
if(arr[rightNodeIndex]>arr[maxIndex]&&rightNodeIndex<size){
maxIndex=rightNodeIndex;
}
//我们来调换位置
if(maxIndex!=index){
int t= arr[maxIndex];
arr[maxIndex] =arr[index];
arr[index]=t;
//调换完之后可能会影响到下面的子树不是大顶堆,我们还需要再次调换
toMaxHeap(arr,size,maxIndex);
}
}
}





程序员灯塔
转载请注明原文链接:数组八大运算
喜欢 (0)