[算法笔记]的笔记 4.1.1 选择排序 4.1.2 插入排序

太过爱你忘了你带给我的痛 2022-04-11 14:23 86阅读 0赞

有童靴发现这一节的代码照抄进去排出来数组的好像不太对~可是又看不出算法有啥问题~

哼，算法当然没问题辣~但是问题在于算法的i从1开始，而数组下标却是从0开始的啦~

所以不能照抄哦，要有适当的改造。

下面贴个完整展示每轮排序的过程：

选择排序：

#include<cstdio>
    using namespace std;
    const int n = 10;
    int A[n]={5,6,2,3,4,9,8,7,1,0};
    void selectSort(){
    	
    		for(int m=0;m<n;m++){
    		printf("%d",A[m]);
    		}
    		printf("\n");
    	
    	for(int i=0;i<n;i++){//n轮排序 
    		int k=i;//假定最值是A[i] 
    		for(int j=i;j<n;j++){//攻擂取代法寻找最小值 
    			if(A[j]<A[k]){//下一个与擂台上的最值比较，胜则取而代之 
    				k = j;
    			}
    		}
    		int temp=A[i];//交换A[k]与A[i] 
    		A[i]=A[k];
    		A[k]=temp;
    		
    		for(int m=0;m<n;m++){
    		printf("%d",A[m]);
    		}
    		printf("\n");
    	}
    
    }
    int main(){
    	selectSort();
    return 0;
    }

运行结果：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N3b3JkdHJhdmVsbGVy_size_16_color_FFFFFF_t_70][]

改造以适应数组后的选择排序算法：（其实就是改了两个for循环）

void selectSort(){
    	for(int i=0;i<n;i++){
    		int k=i;
    		for(int j=i;j<n;j++){
    			if(A[j]<A[k]){
    				k = j;
    			}
    		}
    		int temp=A[i];
    		A[i]=A[k];
    		A[k]=temp;
    	}
    }

插入排序：

#include<cstdio> 
    const int n = 10;
    int A[n]={5,6,2,3,4,9,8,7,1,0};
    void printArray(){
    	for(int k=0;k<n;k++){
    		printf("%d",A[k]);
    	}
    	printf("\n");
    }
    void insertSort(){
    	for(int i=1;i<n;i++){//n-1轮排序,i:1~n-1;每一轮安排一个A[i] 
    		int temp = A[i],j=i;//取A[i],以下j--往前枚举寻找可插入位置 
    		while(j>0 && temp<A[j-1]){//寻找可插入位置
    		//A[i]<A[j-1]则A[i]可以插入到A[j-1]之前的某个位置,这时执行循环体，挪动元素腾出空间 
    		//A[i]>=A[j-1]则A[i]应该插入到A[j-1] 的后一个位置也就是A[j] 
    		//以下是条件成立的循环体 
    			A[j] = A[j-1];//用A[j-1]代替A[j],即A[j-1]后移一位
    			//第一轮while中A[i-1]代替A[i]
    			//第二轮while中A[i-2]代替A[i-1]
    			//如此类推... 
    			j--;//j--,继续循环，继续把元素往后挪动 
    		} 
    		//所有元素挪动完毕，j处可用于插入
    		//以下是条件不成立而退出while以后的插入操作 
    		A[j]=temp; //插入A[i]到A[j] 
    		printArray();
    	}
    }
    int main(){
    	printArray();
    	insertSort();
    	return 0;
    }

运行结果：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N3b3JkdHJhdmVsbGVy_size_16_color_FFFFFF_t_70 1][]

改造后以适应数组后的插入排序算法：（改了for和while循环）

void insertSort(){
    	for(int i=1;i<n;i++){
    		int temp = A[i],j=i;
    		while(j>0 && temp<A[j-1]){
    			A[j] = A[j-1];
    			j--;
    		} 
    		A[j]=temp;
    	}
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N3b3JkdHJhdmVsbGVy_size_16_color_FFFFFF_t_70]: /images/20220411/74dfb7f20d034eaca30958c9c57d9596.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N3b3JkdHJhdmVsbGVy_size_16_color_FFFFFF_t_70 1]: /images/20220411/b992b013555642abb4f18ef5dfeb7abe.png