Java——数组实例（冒泡、选择、插入、快速排序算法）

一、冒泡排序法(从后往前)：

比较相邻的元素，如果第一个比第二个大，就交换他们两个。

对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。针对所有的元素重复以上的步骤,除了最后一个。相同元素的前后顺序并没有改变，所以冒泡排序是一种稳定排序算法。

它的基本思想是，对相邻的元素进行两两比较，顺序相反则进行交换，这样，每一趟会将最小或最大的元素“浮”到顶端，完成最终的排序。

 以上的图片来源于网络，仅供参考，如果原作者对引用感到不满随时可以移除这段文字，谢谢！

冒泡排序法代码实现：

//一、冒泡排序法：
public class text8{
public static void main(String[] args){
	int[] nums= {56,89,12,45,88,99,745,7};//冒泡排序数列：
		for(int i=0;i<nums.length-1;i++){		//外循环控制轮数，比骄轮数即数列的长度减1；
			for(int j=0;j<nums.length-1-i;j++){		//内循环控制次数，即每一轮比较的次数；
				if(nums[j]>nums[j+1]){
					nums[j]=nums[j]+nums[j+1];
					nums[j+1]=nums[j]-nums[j+1];
					nums[j]=nums[j]-nums[j+1];
				}
			}
		}
		System.out.print("冒泡排序法即小到大排列是：");
		for (int n:nums){
			System.out.print(n+"\t");
		}
		System.out.println();
    }
}

排序结果如下：

冒泡排序法即小到大排列是：7    12    45    56    88    89    99    745 

二、选择排序算法：

每一趟从待排序的数据元素中选出最小（或最大）的一个元素；

顺序放在已排好的数列的最后，直到全部待排序的数据元素排完。选择排序是不稳定的排序法.

选择排序（Selection Sort）是一种简单的排序算法，其基本思想是通过找到未排序部分中的最小（或最大）元素，然后将其放置在已排序部分的末尾，以此方式逐步构建有序列表。
以下是选择排序的步骤：
        1.首先，在未排序的部分中找到最小（或最大）的元素。
        2.将找到的最小（或最大）元素与未排序部分的第一个元素交换位置。
        3.现在，第一个元素已经是有序部分的一部分。然后，从剩余未排序的部分中找到最小（或最大）元素。
        4.将找到的最小（或最大）元素与未排序部分的第一个元素之后的元素交换位置。
        5.重复步骤 3-4，直到整个列表有序。
选择排序每次都会将未排序部分的最小（或最大）元素放置在已排序部分的末尾，从而逐步构建有序列表。
        虽然选择排序的实现相对简单，但其时间复杂度为 O(n^2)，在大型数据集上性能较差。
此算法对于小型列表或用作教学示例非常有用，但在实际应用中，更高效的排序算法如快速排序或归并排序通常更受青睐

选择排序法代码实现：

public class test{
public static void main(String[] args){
	    int[] arr= {56,89,12,45,88,99,745,7};//选择排序数列：
//选择排序法；
		int n = arr.length;
        for (int i = 0; i < n - 1; i++) {
            int minIndex = i;
            for (int j = i + 1; j < n; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }
            // 交换元素
            if (minIndex != i) {
                int temp = arr[minIndex];
                arr[minIndex] = arr[i];
                arr[i] = temp;
            }
        }
		System.out.print("选择排序法如下所示：");
		for (int a:number){
			System.out.print(a+"\t");
		}
		System.out.println();
    }
}

排序结果如下：

 选择排序法如下所示：745    99    89    56    88    12    45    7

三、直接插入排序法

（从后向前找到合适位置后插入）：基本思想：每步将一个待排序的记录，按其顺序码大小插入到前面已经排序的子序列的合适位置（从后部向前找到合适位置后），直到全部插入排序完为止。

 以上的图片来源于网络，仅供参考，如果原作者对引用感到不满随时可以移除这段文字，谢谢！

插入排序（Insertion Sort）是一种简单直观的排序算法，它的基本思想是将一个元素逐步插入到已排序部分的正确位置，从而逐步构建有序列表。这种排序类似于我们打扑克牌时整理手牌的方法。
以下是插入排序的步骤：
        1.将列表分为已排序部分和未排序部分。初始时，已排序部分只包含第一个元素，而未排序部分包含剩余的元素。
        2.从未排序部分取出一个元素，称之为“待插入元素”。
        3.将待插入元素与已排序部分的元素从右向左逐个比较，直到找到一个比待插入元素小（或大，根据排序顺序而定）的元素。
        4.将待插入元素插入到找到的位置之后，即完成插入操作。
        5.重复步骤 2-4，直到未排序部分中的所有元素都被插入到已排序部分。
插入排序的特点是，每次将一个元素插入到已排序部分时，已排序部分仍然保持有序。
插入排序在处理小型列表或基本有序的列表时表现良好，但在大型数据集上性能较差。其平均和最坏情况下的时间复杂度都为 O(n^2)。
尽管插入排序不如快速排序或归并排序那样高效，但由于其实现简单，常常在需要稳定的排序结果或者作为其他排序算法的一部分（比如快速排序的优化）时被使用。

直接插入排序法代码如下所示： 

public class test{
public static void main(String[] args){
        int[] arr= {56,89,12,45,88,99,745,7};//插入排序数列：
//插入排序法；
		int n = arr.length;
        for (int i = 1; i < n; i++) {
            int current = arr[i];
            int preIndex = i - 1;
            while (preIndex >= 0 && arr[preIndex] > current) {
                arr[preIndex + 1] = arr[preIndex];
                preIndex--;
            }
            arr[preIndex + 1] = current;
        }
        System.out.println(Arrays.toString(arr));
    }
}

排序结果如下：

插入排序法如下所示：7    12    45    56    88    89    99    745

四、快速排序

/*
* 递归的使用:
*   快速排序
* */
public class Recursion03 {
    public static void main(String[] args) {
        int[] arr = {1,2,6,0,12,15,26,12};
        quickSort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }
 
    // 递归生成斐波那契数列的第 n 个数
    public static void quickSort(int[] arr, int low,int high) {
        // 从左边开始查找
        int left = low;
        // 从右边开始
        int right = high;
        //首先进行每次递归前的判断
        if (low > high){
            return;
        }
        // 参考值【假设是第一个】
        int temp = arr[low];
        // 左小右大
        while (left < right){
            // 开始从右边一个一个的跟参考值做比较，如果右边的数比参考值大，则继续向左移动
            while (temp <= arr[right] && left < right){
                right --;
            }
            // 右指针遇到比参考值小的数时，暂停，进行左指针的判断，如果左边的数比参考值小，则继续向右移动，直到遇到比参考值大的数
            while (temp >= arr[left] && left < right){
                left ++;
            }
            // 走到这里就说明左指针找到了比参考值大的数，右指针找到了比参考值小的数。
            // 如果满足条件则进行以下交换
            if (left < right) {
                int t = arr[left];
                arr[left] = arr[right];
                arr[right] = t;
            }
 
        }
        // 循环结束就代表左指针和右指针相遇了【相等】
        // 所以就可以进行参考值与相等的那个值进行交换了。
        arr[low] = arr[left];
        arr[left] = temp;
        // 递归：负责左边的比较
        quickSort(arr, low,left - 1);
        // 负责右边的比较
        quickSort(arr,left + 1, high);
    }
}

 

四、求一组数中的最大值和最小值

public class test{
public static void main(String[] args){
	int[] num = {56,89,12,45,88,99,745,7};//求最大值和最小值数列；
//求最大值和最小值
	max(num);//调用方法，当输出语句在被调用的方法中时，可以直接写成max(num);
	//System.out.println(max);当在此写输出语句时，需要在前面写：int max = max(num);
	
	int min = min(num);
	System.out.println("最小值是："+min);
//以下既是最大值最小值的方法：
	public static int max(int[] num){
		int len = num.length;
		int max = num[0];
		for(int i = 1;i<len;i++){
			if(num[i]>max){
				num[i]= num[i]+max;
				max = num[i]-max;
				num[i]=num[i]-max;								
			}
		}
		System.out.println("最大值是："+max);
		return max;
	}
	
	public static int min(int[] num){
		int len = num.length;
		int min = num[0];
		for(int i = 1;i<len;i++){
			if(num[i]<min){
				num[i]= num[i]+min;
				min = num[i]-min;
				num[i]=num[i]-min;								
			}			
		}		
		return min;
	}
}

输出结果如下：

 最大值是：745
 最小值是：7

 支持：