插入排序，选择算法与快速排序（c语言，Java语言）

插入排序

原理：从数组的第二个元素开始，将数组中的每个元素按照（升序或降序）规则插入到已排序的数组中，以达到排序的目的。

插入排序并不是取出元素，插入到适当的位置，然后为后续元素的位置加一。相反，元素会成对比较，直到它们交换到适当的位置。没有移动元素位置的过程，只有元素值的交换。宏观上就像取出和插入，所以称为插入排序。

上图中，数组7,6,9,3…按照升序排列，那么7就看成是已经升序排列的元素数组，从第二个元素开始比较，则6< 7应该在7之前“插入”到7​​中，因此在6和7之间交换元素相当于在7之前插入6。

第三个元素是9，大于7，无需移动，后一个元素是3，该元素需要与其位置之前的所有元素比较，而且是比较一次交换依次，而不是直接插入到6之前。过程是前与9比较小于然后交换值，然后在该位置在与前一个元素比较判断是否交换，也就是说每次比较符合条件，则向前移动一位，下一次比较再从当前位置与前一位比较，以此类推。

每次分配都是成对交换，总共需要n次循环。每个元素需要依次与其先前或更改的元素进行比较。

//核心比较部分
for(i=0;i<len;i++){
        //一共需要比较的总次数
		for(j=i;j>0;j--){
         //每个元素还需与其前的元素比较
			if(a[j] < a[j-1]){
    
				int tmp = a[j];
				a[j]= a[j-1];
				a[j-1] = tmp;
			}
		}
	}

1. c语言实现

#include<stdio.h>

int main(){
    
	int i,j;
	int a[]= {
    7,6,9,3,1,5,2,4};
	int len = sizeof(a)/sizeof(int);
	for(i=0;i<len;i++){
    
		for(j=i;j>0;j--){
    
			if(a[j] < a[j-1]){
    
				int tmp = a[j];
				a[j]= a[j-1];
				a[j-1] = tmp;
			}
		}
	}
	for(i=0;i<len;i++){
    
		printf("%d,",a[i]);
	}
	printf("\n");
} 

2. java实现

public class InsertSort {
    
    public static void main(String args[]){
    
        int a[]=new int[]{
    7,6,9,3,1,5,2,4};
        insertSort(a);
        for (int i =0;i<a.length;i++){
    
            System.out.print(a[i]+"~");
        }

    }

    /** * @description 插入算法 * 核心:从第一位为元素开始当作已排序的数组，之后的元素依次与之前元素比较直到大于前者，小于后者（或者大于前者小于后者），满足则交换元素的值。 * 比较是两脸个比较的，因此循环比较完的元素是排序好的，在宏观上相当于将元素取出来插入到合适的位置 */
    public static void insertSort(int a[]){
    
        for (int i =1;i<a.length;i++){
         //对于每一个元素都需要取出判断
            for (int j=i;j>0;j--){
             //每个元素需要依次与其前的元素比较直到插入到合适位置
                if(a[j] <a[j-1] ){
    
                    int tmp = a[j];
                    a[j] = a[j-1];
                    a[j-1] = tmp;
                }
            }
        }
    }
}

对于n个元素的数组，插入排序需要外层循环n次，内层循环约n-1次，所以时间复杂度为：

$$氧（n）=n^2$$

选择排序

原理：选择排序选择未排序数组开头最小的一个。

如图所示，从数组中选择最小的1，将其放置在数组的起始位置，则该位置将被视为已排序的数组，然后从剩余数​​组中选择最小的1，继续将其放置在初始位置等。

对于一个数组，需要找到n个元素中最小的一个，每次寻找最小的需要n-i次。

1. c语言实现

#include<stdio.h>

int main(){
    
	int i,j;
	int a[]= {
    7,4,5,9,8,2,1};
	int len = sizeof(a)/sizeof(int);
	for(i=0;i<len;i++){
          //依次取出n个元素
		for(j=i;j<len;j++){
        //对每个元素于剩余元素作比较取最小值
			if(a[i] > a[j]){
    
				int tmp = a[i];
				a[i]= a[j];
				a[j]= tmp;
			}
		}
	}
	for(i=0;i<len;i++){
    
		printf("%d",a[i]) ;
	}
}

2. java实现

package 选择排序;

public class QuickSort {
    
    public static void main(String[] args) {
    
        int a[] = new int[]{
    7,4,5,9,8,2,1};
        for (int i =0;i< a.length;i++){
    
            for(int j =i+1;j<a.length;j++){
    
                if(a[i]<a[j]){
    
                    int tmp = a[i];
                    a[i] = a[j];
                    a[j] = tmp;
                }
            }
        }

        for (int i=0;i<a.length;i++){
    
            System.out.print(a[i]+",");
        }
    }
}