/------------------冒泡排序
外层 len - 1   里层  j < len - i - 1

大数下沉

1)比较相邻的元素。如果第一个比第二个大,就交换他们两个。

2)对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。
在这一点,最后的元素应该会是最大的数。

3)针对所有的元素重复以上的步骤,除了最后一个。
4)持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。

/*  78 10 15 65 3      //len = 5    len - 1 = 4//外层循环了len-1  次
----------------------
    10 15 65 3  78     //循环了4ci   // 内层循环了len - i -1次
--------------------
    10 15 3  65  78    //循环了3次
--------------------
    10 3 15 65  78     //循环了2次
---------------------
    3 10 15 65  78     //循环了1次

*/



for (int i=0; i<len-1; i++)
//每趟排序都会确定一个数,所以需要再循环len-i次,但因为每次都是 //相邻的两个数进行比较,为了a[j+1]不越界,让j循环到len-i-1时停止。
    for (int j=0; j<len-i-1; j++) {
   
    //若arr[j]>arr[j+1] 若前一位比后一位元素大,则交换顺序
    if (arr[j]>arr[j+1]) {
        
        int temp = arr[j];
        
        arr[j] = arr[j+1];
        
        arr[j+1] = temp;
    }


//------------------选择排序思想
外层 len-1   里层  j=i+1  j<len
   
   
    int a[10]={23,12,4,67,20,100,21,45,3,28};
   
    假设a[0]为最小,分别与a[1] a[2] ... 比较,  在比较过程中,如果有元素的值比a[0]小,交换值

第一种方法
//每一趟都是拿着一个元素与后面其他元素进行比较,找出最小值
    void selectSort1(int array[],int len){
    // 1、确定需排序趟数
    for (int i = 0 ; i < len - 1; i++) { // 2、每一趟怎么处理
        
        for (int j = i + 1; j < len; j++) {
            
            if (array[i] > array[j]) {
               
            int temp = array[i];
               
                array[i] = array[j];
               
                array[j] = temp;
        }
        }
    }
}

第二种方法
void selectSort2(int arr[],int len){
    int temp;
    int min;
    for (int i=0; i<len - 1; i++) {
        //每次假设第arr[i]是最小值 min = i;
        min = i;
        for (int j=i+1; j<len; j++) {
            //找到最小的那个元素的下标
            if (arr[j]<arr[min]) min=j;
        }
        //如果没有找到比arr[i]小的,就不用交换 if(i!= min){
        //将第i个元素和最小的元素交换 temp=arr[i];
        temp = arr[i];
        
        arr[i]=arr[min];
        
        arr[min] = temp; }
}
//打印数组
for (int i=0; i<len; i++) {
    printf("%d\t",arr[i]); }
}



//-----    冒泡:
        外层for (int i=0; i<len-1; i++)
            内层for (int j=0; j<len-i-1; j++)
   
//-----    选择排序:
        外层for (int i=0; i<len - 1; i++)
            内层for (int j=i+1; j<len; j++)


//------------------折半查找思想

思路:   先划分空间,再在其空间查找,取中间点,中间点往左,元素的值一定比中间值小,右边的值一定比中间值大.
    判断 关键点  if (key>arr[mid]) {low = mid+1;}    //右半区查找
               if (key<arr[mid]){high = mid - 1;}  //左半区查找




找 12
   low                                  high
    0   1    2   3  4    5  6   7   8    9
//  3        4        12        20        21        23        28        45        67        100
--------------------------------------------
1  low             mid                   high
2  low mid      high
3           low high

mid = (low + high) / 2  = 4;

a[4] = 21 > 12  -->  high = mid - 1  --->  4 - 1 = 3
mid = (low + high)/2 = 1;

a[1] = 4 < 12  -->   low = mid + 1 -->  1+1 = 2
mid = (2+3)/2 --> 2

a[2] = 12 == 12

//折半查找
int searchItem(int arr[],int len,int key){
   
    //先要定义变量
    int low=0,high=len-1,mid;
   
    //循环
    while (low<=high) {
        
        // 计算 mid的位置
        mid = (low+high)/2;
        
        printf("mid = %d",mid);
        
        // 判断 key a[mid],右半区查找
        if (key>arr[mid]) {
            // key > a[mid]     low = mid +1;
            low = mid+1;
        }else if (key<arr[mid]){
            // key < a[mid]     high = mid -1;
            high = mid - 1;
        }else{
            // key == a[mid]    //return mid;
            return mid;
        }
    }
   
    // 下面是查找不到的情况
    return -1;
}

//折半插入  不建议看
int insertItemLoc(int arr[],int len,int key){
   
    //先要定义变量
    int low=0,high=len-1,mid;
   
    //循环
    while (low<=high) {
        
        // 计算 mid的位置
        mid = (low+high)/2;
        
        // 判断 key a[mid],右半区查找
        if (key>arr[mid]) {
            // key > a[mid]     low = mid +1;
            low = mid+1;
        }else if (key<arr[mid]){
            // key < a[mid]     high = mid -1;
            high = mid - 1;
        }else{
            // key == a[mid]    //return mid;
            return mid + 1;
        }
    }
   
    // 下面是查找不到的情况
    return low;
}

学习学习！！！