Java数组之排序操作及部分习题总结
程序员文章站
2024-03-08 10:15:58
...
排序操作
目录
选择排序
冒泡排序
插入排序
计数排序
习题总结
选择排序
选择排序：是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到全部待排序的数据元素排完。 选择排序是不稳定的排序方法。
举个例子：
[8,5,9,2,7,4,6,1,3 ]
第一次：[1 5 9 2 7 4 6 8 3]
第二次：[1 2 9 5 7 4 6 8 3]
第三次：[1 2 3 5 7 4 6 8 9]
第四次：[1 2 3 4 7 5 6 8 9]
第五次：[1 2 3 4 5 7 6 8 9]
第六次：[1 2 3 4 5 6 7 8 9]
代码实现如下：
class Test{
public static void main(String[] args){
//选择排序O(n^2)
selectSort();
}
public static void selectSort(){
int[] arr={8,5,9,2,7,4,6,1,3};
for(int i=0;i<arr.length-1;i++){//-1是因为没有必要进行最后一个数字的比较
for(int j=i+1;j<arr.length;j++){
if(arr[i]>arr[j]){
swap(arr,i,j);//即用-即释放
}
}
}
show(arr);
}
public static void swap(int[] arr,int i,int j){
arr[i]=arr[i]+arr[j];
arr[j]=arr[i]-arr[j];
arr[i]=arr[i]-arr[j];
}
public static void show(int[] arr){
//[1,2,3,4,5,6,7,8,9]
String s="[";
for(int i=0;i<arr.length;i++){
if(i==arr.length-1){
s+=arr[i]+"]";
}else{
s+=arr[i]+",";
}
}
System.out.println(s);
}
}
冒泡排序
冒泡排序：对比相邻的元素值，如果满足条件就交换元素值，把较小的元素移动到数组的前面（从小到大排序），把大的元素移动到数组的后面，即交换两个元素的位置，这样较小的元素就像气泡一样从底部上升到顶部。
举个例子：
{8,5,9,2,7,4,6,1,3}
第一次：{5 8 2 7 4 6 1 3 9}
第二次：{5 2 7 4 6 1 3 8 9}
第三次：{2 5 4 61 3 7 8 9}
第四次：{2 4 5 1 3 6 7 8 9}
第五次：{2 4 1 3 5 6 7 8 9}
第六次：{2 1 3 4 5 6 7 8 9}
第七次：{1 2 3 4 5 6 7 8 9}
代码实现如下：
class Test{
public static void main(String[] args){
//冒泡排序O(n^2)
bubbleSort();
}
public static void bubbleSort(){
int[] arr={8,5,9,2,7,4,6,1,3};
for(int i=0;i<arr.length-1;i++){//-1是少一轮比较
for(int j=0;j<arr.length-1-i;j++){//-1避免重复比较和角标越界
if(arr[j]>arr[j+1]){
swap(arr,j,j+1);
}
}
}
show(arr);
}
public static void swap(int[] arr,int i,int j){
int temp=arr[i];
arr[i]=arr[j];
arr[j]=temp;
}
public static void show(int[] arr){
//[1,2,3,4,5,6,7,8,9]
String s="[";
for(int i=0;i<arr.length;i++){
if(i==arr.length-1){
s+=arr[i]+"]";
}else{
s+=arr[i]+",";
}
}
System.out.println(s);
}
}
插入排序
插入排序：描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。
代码实现如下:
class Test{
public static void main(String[] args){
//插入排序O(n^2)
insertSort();
}
public static void insertSort(){
int[] arr={8,5,9,2,7,4,6,1,3};
int e;
int j;
for(int i=1;i<arr.length;i++){
e=arr[i];
for(j=i;j>0&&arr[j-1]>e;j--){
arr[j]=arr[j-1];
}
arr[j]=e;
}
show(arr);
}
public static void swap(int[] arr,int i,int j){
arr[i]=arr[i]+arr[j];
arr[j]=arr[i]-arr[j];
arr[i]=arr[i]-arr[j];
public static void show(int[] arr){
//[1,2,3,4,5,6,7,8,9]
String s="[";
for(int i=0;i<arr.length;i++){
if(i==arr.length-1){
s+=arr[i]+"]";
}else{
s+=arr[i]+",";
}
}
System.out.println(s);
}
}计数排序
计数排序：计数排序是一个非基于比较的排序算法，计数排序的基本思想是：对于给定的输入序列中的每一个元素x，确定该序列中值小于x的元素的个数。有了这个信息之后，就可以将x直接存放到最终的输出序列的正确位置上。
代码实现如下：
class Test{
public static void main(String[] args){
//计数排序O(n+m)
countSort();
}
public static void countSort(){
int[] arr={8,5,9,2,7,4,6,1,3,10,-3,-2,-10};
int min=arr[0];
int max=arr[0];
for(int i=0;i<arr.length;i++){//O(n)
if(arr[i]>max){
max=arr[i];
}
if(arr[i]<min){
min=arr[i];
}
}
int[] nums=new int[max-min+1];
int offset=min;
for(int i=0;i<arr.length;i++){//O(n)
nums[arr[i]-offset]++;
}
int index=0;
for(int i=0;i<nums.length;i++){//O(m)
if(nums[i]!=0){
for(int j=0;j<nums[i];j++){
arr[index++]=i+offset;
}
}
}
show(arr);
}
public static void swap(int[] arr,int i,int j){
arr[i]=arr[i]+arr[j];
arr[j]=arr[i]-arr[j];
arr[i]=arr[i]-arr[j];
}
public static void show(int[] arr){
//[1,2,3,4,5,6,7,8,9]
String s="[";
for(int i=0;i<arr.length;i++){
if(i==arr.length-1){
s+=arr[i]+"]";
}else{
s+=arr[i]+",";
}
}
System.out.println(s);
}
}
习题总结
import java.util.*;
class Demo05_01{
public static void main(String[] args){
/*
数组长度不固定 需要读取一个数据 数组扩容 填入数据
数据填入之后进行排序 然后遍历数组依次判断数据的个数
连续相等
*/
Scanner scanner = new Scanner(System.in);
int[] arr=new int[0];
System.out.print("Enter numbers:");//1.获取用户输入的数据 动态的扩容数组填充数据
while(true){
int num=scanner.nextInt();
if(num==0){
break;
}
//验证用户输入数据的正确性
if(num<1||num>100){
System.out.println("有非法数据！");
return;
}
arr=copyOf(arr,arr.length+1);
arr[arr.length-1]=num;
}
//2.按照输出结果 将数据中的数据进行排序
insertSort(arr);
//3.输出连续相等的数字
show(arr);
}
public static int[] copyOf(int[] arr,int newLen){
int[] newArr=new int[newLen];
for(int i=0;i<arr.length;i++){
newArr[i]=arr[i];
}
return newArr;
}
public static void insertSort(int[] arr){
for(int i=1;i<arr.length;i++){
int e=arr[i];
int j;
for(j=i;j>0&&arr[j-1]>e;j--){
arr[j]=arr[j-1];
}
arr[j]=e;
}
}
public static void show(int[] arr){
System.out.println(Arrays.toString(arr));
for(int i=0;i<arr.length;){
int count=1;
for(int j=i+1;j<arr.length;j++){
if(arr[j]==arr[i]){
count++;
}else{
break;
}
}
System.out.println(arr[i]+" occurs "+count+(count>1?" times":" time"));
i+=count;
}
}
}
import java.util.*;
class Demo05_02{
public static void main(String[] args){
/*
在全部输入之后去重复
*/
func1();
}
public static void func1(){
//1.循环遍历数组进行赋值
Scanner scanner = new Scanner(System.in);
System.out.print("Enter numbers:");
int[] arr = new int[10];
for(int i = 0;i < arr.length;i++){
arr[i] = scanner.nextInt();
}
}
public static void method3(int[] arr){
//不创建额外空间 不许改变原先的顺序
int i=0;
int size=arr.length;
while(i<size){
for(int j=i+1;j<size;){
if(arr[j]==arr[i]){
for(int k=j+1;k<size;k++){
arr[k-1]=arr[k];
}
size--;
}else{
j++;
}
}
i++;
}
for(i=0;i<size;i++){
System.out.print(arr[i]+" ");
}
}
public static void method2(int[] arr){
//插入排序
for(int i=1;i<arr.length;i++){
int e=arr[i];
int j;
for(j=i;j>0&&arr[j-1]>e;j--){
arr[j]=arr[j-1];
}
arr[j]=e;
}
//连续相等
for(int i=0;i<arr.length;){ //O(n)
System.out.print(arr[i]+" ");
int count=1;
for(int j=i+1;j<arr.length;j++){
if(arr[j]==arr[i]){
count++;
}else{
break;
}
}
i+=count;
}
}
public static void method1(int[] arr){
int[] newArr=new int[0];
for(int i=0;i<arr.length;i++){ //O(n)
if(!contains(newArr,arr[i])){ //O(m)
newArr=copyOf(newArr,newArr.length+1);
newArr[newArr.length-1]=arr[i];
}
}
System.out.println(Arrays.toString(newArr));
}
public static boolean contains(int[] arr,int key){
for(int i=0;i<arr.length;i++){
if(arr[i]==key){
return true;
}
}
return false;
}
public static int[] copyOf(int[] arr,int newLen){
int[] newArr=new int[newLen];
for(int i=0;i<arr.length;i++){
newArr[i]=arr[i];
}
return newArr;
}
}
import java.util.*;
class Demo05_03{
public static void main(String[] args){
//1.获取用户的输入 只不过第一个输入的数据时数据的个数(数组的长度)
Scanner scanner=new Scanner(System.in);
System.out.print("Enter a list:");
int len=scanner.nextInt();//获取的第一个数值就是数组的长度
int[] arr=new int[len];
for(int i=0;i<arr.length;i++){
arr[i]=scanner.nextInt();
}
//2.对数组进行有序的判断
if(isSorted(arr)){
System.out.println("The list is already sorted.");
}else{
System.out.println("The list is not sorted.");
}
}
public static boolean isSorted(int[] list){
//如果不是升序排列 那么势必会出现有一组数据 左大右小的情况
for(int i=1;i<list.length;i++){
if(list[i-1]>list[i]){
return false;
}
}
return true;
}
}
import java.util.*;
class Demo05_04{
/*
输入的数据：槽子的个数 球的个数=路径的个数
创建槽子的具体的容器int[]
每一个小球下落的路径L R 字符串
对于每一个小球而言其路径中的步骤是随机产生L R
*/
public static void main(String[] args){
//1.提示用户输入槽子的个数和小球的个数
Scanner scanner=new Scanner(System.in);
System.out.print("Enter the number of balls to drop:");
int balls=scanner.nextInt();
System.out.print("Enter the number of slots in the bean machine:");
int slots=scanner.nextInt();
//2.根据已有的槽子的个数去创建槽子容器.
int[] arr=new int[slots];
//3.几个球几个路径path
for(int i=0;i<balls;i++){
String path=getPath(slots);
System.out.println(path);
//5.只要看当前路径中R的个数即可
arr[getR(path)]++;
}
//6.输出
System.out.println(Arrays.toString(arr));
show(arr);
}
public static void show(int[] arr){
int w=arr.length;
int h=0;
for(int i=0;i<arr.length;i++){
if(arr[i]>h){
h=arr[i];
}
}
for(int i=h-1;i>=0;i--){
for(int j=0;j<w;j++){
if(i<arr[j]){
System.out.print("O");
}else{
System.out.print(" ");
}
}
System.out.println();
}
}
public static int getR(String path){
int count=0;
for(int i=0;i<path.length();i++){
if(path.charAt(i)=='R'){
count++;
}
}
return count;
}
public static String getPath(int slots){
//4.根据槽子的个数计算每一个球下落的路径
Random random=new Random();
String path="";
for(int j=0;j<slots-1;j++){
if(random.nextInt(2)==0){ //向左
path+="L";
}else{ //向右
path+="R";
}
}
return path;
}
}