java 算法学习 --- 常用的算法

川长思鸟来 2021-09-26 23:08 283阅读 0赞

编程语言的几种基本算法主要有以下几个：

1、 插入排序(直接插入排序、 希尔排序)

2、 交换排序(冒泡排序、快速排序)

3、 选择排序（直接选择排序、 堆排序）

4、 归并排序

5、 分配排序（箱排序、 基数排序）

按照条件来使用排序算法：

所需辅助空间最多： 归并排序

所需辅助空间最少：堆排序

平均速度最快： 快速排序

不稳定： 快速排序、 希尔排序、 堆排序

选择排序算法的时候：

1、数据的规模

2、数据的类型

3、数据已有的顺序

一般来说， 当数据规模较小时，应该直接插入排序或冒泡排序。  任何排序算法在数据量小时基本体现不出来差距。  考虑数据的类型，比如如果全部是正整数， 那么考虑使用桶排序最优。  考虑数据已有顺序， 快速排序是一种不稳定的排序（可以改进），对于大部分排好的数据， 快速排序会浪费大量不必要的步骤。 数据量极小，而且已经基本排好序， 冒泡是最佳选择。 我们说快速排序好， 是指大量随机数据下，快速排序效果最理想。 而不是所有情况。

### 一、 插入排序 ###

1、 直接插入排序

讲一个记录插入到已经排好序的有序表中。

① sorted数组的第0个位置没有放数据

② 从sorted第二个数据开始处理； 如果该数据比它前面的数据要小，说明该数据要往前面移动。

步骤：

a. 首先将数据备份放到sorted的第0个位置当哨兵

b. 然后将该数据前面那个数据后移

c. 然后往前搜索， 找到插入位置

d. 找到插入位置之后讲， 第0个位置的那个数据插入对应位置。

时间复杂度： O（n\*n）， 当待排记录序列为正序时， 时间复杂度提高至O（n）

![70][]

直接插入排序例子  java语言实现

public class InsertionSort {
    	
    	//插入排序： 直接插入排序， 希尔排序
    	public static void straighInsertionSort(double[] sorted){
    		int length = sorted.length;
    		for(int i=2; i<length; i++){  //数组的第0个下标没有放数据，从第二个数据开始
    			
    			if(sorted[i] < sorted[i-1]){
    				sorted[0] = sorted[i];   //设置哨兵
    				sorted[i] = sorted[i-1]; //将数据前面那个数据后移一位
    				
    				int insert = 0;
    				for(int j=i-2; j>=0; j--){
    					if(sorted[j] > sorted[0]){
    						sorted[j+1] = sorted[j];  //后移一位
    					}else{
    						insert = j+1;  //插入的位置
    						break;
    					}
    				}
    				sorted[insert] = sorted[0];
    			}
    		}
    	}
    	
    	public static void main(String[] args) {
    		Random random = new Random(6);
    		int arraySize = 21;
    		double[] sorted = new double[arraySize];
    		
    		System.out.println("排序前:");
    		for(int i=1;i<arraySize; i++){
    			sorted[i] = (int)(random.nextDouble()*100);
    			System.out.print((int)sorted[i] + " ");
    		}
    		System.out.println();
    		
    		InsertionSort.straighInsertionSort(sorted);
    		System.out.println("排序后：");
    		for (int i = 1; i < sorted.length; i++) {
    			System.out.print((int)sorted[i] + " ");
    		}
    		System.out.println();
    	}
    }

测试结果：

![70 1][]

2、希尔排序(缩小增量排序)

先将整个待排记录序列分割成若干个子序列分别进行直接插入排序，待整个序列中的记录基本有序时，再对全体记录进行一次直接插入排序。

例子：

### 二、交换排序 ###

1、冒泡排序

冒泡排序是专门针对一部分排序的数据进行排序的一种排序算法，如果在你的数据清单中只有一两个数据是乱序的话，用这种算法就是最快的排序算法。  如果你的数据清单中的数据是随机排列的，那么这种方法就成了最慢的算法了，因此在使用这种算法之前一定要慎重，这种算法的核心思想是扫描数据清单，寻找出乱序的两个相邻的项目，当找到这两个项目后，交换项目的位置然后继续扫描，重复上面的操作直到所有的项目都按顺序排序好。

![70 2][]

例子：java语言：

/**
     * 冒泡排序
     * @author Administrator
     *
     */
    public class Bubble {
    	/**
    	 * 原理：相邻元素两两比较，大的往后放，第一次扫描完毕后，最大值就在数组的
    	 * 最大索引值处(即数组[数组长度-1]),然后重复上面的步骤
    	 * 
    	 * 规律：
    	 * 1. 两两比较，大的王后放
    	 * 2. 第一次比较完毕后，下一次比较的时候就会减少一个元素的比较
    	 * 3. 假如有5个数需要比较
    	 * 	  第①趟 ： 需要两两比较4次
    	 * 	  第②躺 ： 需要两两比较3次
    	 * 	  第③趟 ： 需要两两比较2次
    	 * 	  第④趟 ： 需要两两比较1次  最后一趟
    	 * 所以得出规律： 总共比较趟数为   数组长度-1次
    	 * 			 每趟需要比较次数为  数组长度-趟数 
    	 * @param sort
    	 */
    	public static void bubbleSort(int[] sort){
    		int length = sort.length;
    		
    		for(int i=1;i<length-1;i++){
    			
    			for(int j=1; j<length-i; j++){
    				
    				if(sort[j] > sort[j+1] ){
    					//交换位置
    					int temp = sort[j];
    					sort[j] = sort[j+1];
    					sort[j+1] = temp;
    				}
    				
    			}
    		}
    	}
    }

测试：

int[] sort;
    	int sortSize = 21;
    	Random random = new Random(30);
    	
    	@Before
    	public void init(){
    		sort = new int[sortSize];
    		System.out.println("排序前：");
    		for(int i=1; i < sortSize; i++){
    			sort[i] = (int)(random.nextDouble()*100); 
    			System.out.print(sort[i] + " ");
    		}
    		System.out.println();
    	}
    	
    	@Test
    	public void testBubbleSort(){
    		long start = System.currentTimeMillis();
    		Bubble.bubbleSort(sort);
    		long end = System.currentTimeMillis();
    		System.out.println("冒泡排序后：");
    		
    		for (int i = 1; i < sortSize; i++) {
    			System.out.print(sort[i]+ " ");
    		}
    		System.out.println();
    		System.out.println("冒泡排序时间：" + (end - start) + "ms");
    	}

结果：

![70 3][]

### 三、归并排序 ###

[多路归并排序][Link 1]

[70]: /images/20210923/329870ea565b4bf384f317ea980a02a6.png
[70 1]: /images/20210923/8f1d41ed07cb4b43893b4bfc9e7528c2.png
[70 2]: /images/20210923/6dffd3de20934976a94dde444b64844e.png
[70 3]: /images/20210923/753e1c03902c406a941fe2d9bb7e3ee3.png
[Link 1]: https://blog.csdn.net/wawawawawawaa/article/details/113714254?spm=1001.2014.3001.5501