【21天学习挑战赛】顺序查找

一维数组元素查找方式

顺序查找

从数组的一边开始，逐个进行元素比较，直到要查找的元素和给定元素相同则查找成功，如果查找完毕后仍未找到匹配元素则查找失败。

二分查找

在元算有序的前提下，尽可能缩小范围，提高查找效率。

索引查找

对于无序的数据集合，先建立索引表，是的索引表有序或者分块有序，结合顺序查找和索引查找完成查找。

顺序查找

输入：n个数字（无序）。
输出：查找成功则输出下标，失败则返回-1。

int nums[10],x;
cin>>x;
for(int i=0;i<nums.size();i++){
  if(x==nums[i]) return i;

return -1;

空间复杂度上面仅仅引入i这个变量为O（1）。
时间复杂度为最坏情况下的O（n）

插入排序

原理：每次插入一个元素，每一趟完成对一个待排元素的放置，直到全部插入完成。

直接插入排序

将每个待排元素插入到已知的已经排好的序列中。（每次从原有数据中取出一个新排列，插入到之前已经排好的序列中，直到所有数字取完，这个新排列就完成了）

算法详解：
假设前面 n-1(其中 n>=2)个数已经是排好顺序的，现将第 n 个数插到前面已经排好的序列中，然后找到合适自己的位置，使得插入第n个数的这个序列也是排好顺序的。

从小到大的插入排序整个过程如图示：

第一轮：从第二位置的 6 开始比较，比前面 7 小，交换位置。

第二轮：第三位置的 9 比前一位置的 7 大，无需交换位置。

第三轮：第四位置的 3 比前一位置的 9 小交换位置，依次往前比较。

第四轮：第五位置的 1 比前一位置的 9 小，交换位置，再依次往前比较。

public class InsertionSort {
    
    public static void sort(Comparable[] arr){
    
    
        int n = arr.length;
        for (int i = 0; i < n; i++) {
    
            // 寻找元素 arr[i] 合适的插入位置
           for( int j = i ; j > 0 ; j -- )
                if( arr[j].compareTo( arr[j-1] ) < 0 )
                    swap( arr, j , j-1 );
                else
                    break;
        }
    }
    //核心代码---结束
   }
 }

折半插入排序

由于在插入排序的过程中，已经生成一个有序序列。所以在插入待排序元素时用折半查找能更快确定新元素的位置。当元素个数较多的时候，折半插入排序优于直接插入排序。

希尔排序

将全部元素分成几组之后，在每一组内使用直接插入排序，然后继续减少间距，形成新的分组进行排序，直到间距为0为止。