直接插入排序和简单选择排序

野性酷女 2021-10-29 23:44 280阅读 0赞

简单选择排序的思想：  
简单选择排序的基本思想是每一趟在 n-i+1个记录中选取关键字最小的记录作为有序序列的第i个记录

直接插入排序思想：  
基本操作是将一个记录插入到已经排好序的有序表中，从而得到一个新的，记录加1的有序表。

两者都是第二for循环都是不断查找，一个是不断往后找，一个在当前i，不断往前找。  
简单选择排序，就是在当前选择i的时候，从后序的n-i+1个记录中查找最小的那个数，插入当前位置。

// 简单选择排序： 每一趟在n-i+1个记录中选择关键字最小的记录 作为有序序列的第i个记录。
            public void SelectSort(int[] nums)
            {
                int i,j,min;
    
                for(i = 0;i<nums.length;i++)
                {
                    min = i;   //每一次插入
                    for(j = i+1;j<nums.length;j++) //都从后续的序列中找到最小的min
                    {
                        if(nums[min]>nums[j])
                            min = j;
                    }
                    if(i!=min){                 // i!=min  即找到,否则 当前最小
                        swap(nums,i,min);
                    }
                }
    
                prints(nums);
            }

直接插入查找，就是当前i位置时，不断往前找一个合适的（已经有序的位置插入）.  
int temp = nums\[i\],  
for（j = i-1;j>=0;j–）  
if(nums\[j\]>temp)  
nums\[j+1\] = nums\[j\];//移动元素  
else  
break; //找到当前j 是小于 i位置的一个元素，所以插入nums\[j+1\] = temp;

// 直接插入排序
            public void InsertSort(int[] s){
    
                int i,j;
                for(i = 1;i<s.length;i++)
                {
                    int temp = s[i];  // 存下当前的数
                    for(j = i-1;j>=0;j--)
                    {
                        if(s[j]>temp)
                        {
                            s[j+1] = s[j];// 大于temp的数后移
                        }else{
                            break;
                        }
                    }
                    // 插入
                    s[j+1] = temp;
                }
                prints(s);
            }

不同：很容易弄混.把直接插入排序，当成简单选择排序，  
因名知意，选择就是从后选择，选择最小的元素，插入当前位置。  
而插入排序，则是找个合适的位置，插入，具体怎么插入，怎么移动。从这方面思考。