排序算法

排序算法的概念， 我们将对数组进行排序来实现几种不同的排序算法，让大家更好的体会不同算法中的执行过程

冒泡排序

概念

1、比较相邻的元素。如果第一个比第二个大，就交换他们两个。
2、对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
3、针对所有的元素重复以上的步骤，除了最后一个。
4、持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

速记口诀:N 个数字来排队,两两相比小靠前,外层循环 N-1,内层循环 N-1-I

动图演示

实现思路

根据动图演示分析，由于每次循环都只会找最大值或者最小值，所以我们采用二重循环进行实现
实现注意点：控制比较多少轮，控制每轮比较多少次，什么情况下交换顺序交换数据

实现代码

int[] nums = { 3,1,5,6,2};
        for (int i = 0; i < nums.length; i++) {
            for (int j = 0; j < nums.length - 1 - i; j++) {
                if (nums[j] > nums[j+1]){//升序，降序只需将本行大于号改小于号
                    //使用第三个变量进行两数交换
                    int temp = nums[j];
                    nums[j] = nums[j+1];
                    nums[j+1] = temp;
                    /*
	                    //不使用第三个变量进行两数交换
	                    nums[j] = nums[j] + nums[j+1];
	                    nums[j+1] = nums[j] - nums[j+1];
	                    nums[j] = nums[j] - nums[j+1];
                    */
                }
            }
        }
System.out.println(Arrays.toString(nums)); //[1, 2, 3, 5, 6]

插入排序

概念

指在待排序的元素中，假设前面n-1(其中n>=2)个数已经是排好顺序的，现将第n个数插到前面已经排好的序列中，然后找到合适自己的位置，使得插入第n个数的这个序列也是排好顺序的。按照此法对所有元素进行插入，直到整个序列排为有序的过程

动图演示

实现思路

根据动图演示分析，循环数组时，会将数组分为两段，前面一段为有序列表，后面一段为无序列表，每次都将后面无序列表中的第一个值取出并给这个值给定一个临时下标，然后与前面的有序列表进行一一比较，当前值小于比较值就将比较的值的下标+1，而循环值的临时下标-1
实现注意点：循环数组时，下标从1开始

实现代码

int[] nums = { 3,1,5,6,2};
       for (int i = 1; i < nums.length; i++) {
           int insertValue = nums[i]; //待插入的值，也就是数组中的第一个值
           int insertIndex = i - 1;   //待比较值的下标  初始值是有序列表最后一个值的下标
           while(insertIndex >= 0 && insertValue < nums[insertIndex]){
               nums[insertIndex+1] = nums[insertIndex];
               insertIndex--;
           }
           nums[insertIndex + 1] = insertValue;
       }
System.out.println(Arrays.toString(nums));

选择排序

概念

首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

动图演示

实现注意点：循环数组时，循环次数小于数组长度-1

实现代码

int[] nums = { 3,1,5,6,2};
      for (int i = 0; i < nums.length - 1; i++) {
          //每次循环将第一个值当做最小值，将最小值的下标存入min
          int min = i;
          for (int j = i + 1; j < nums.length; j++) {
              if (nums[min] < nums[j]){
                  min = j;
              }
          }
          if (min != i){
              int temp = nums[i];
              nums[i] = nums[min];
              nums[min] = temp;
          }
      }
System.out.println(Arrays.toString(nums));

查找算法

二分查找法

概念

一种在有序数组中查找某一特定元素的搜索算法。搜索过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空，则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。

动图演示

实现注意点：查找的数组是一个有序数组

public static void main(String[] args) {
       int[] nums = { 1,3,5,7,9,11,13};
       int value = 9;
       int index = getIndex(nums, value);
       System.out.println("value在nums数组中的下标为：" + index);
   }
public static int getIndex(int[] nums,int value){
     int min = 0;
     int max = nums.length - 1;
     while (true){
         int mid = (min + max) / 2;
         if (nums[mid] == value){
             return mid;
         }else if (nums[mid] > value){
             max = mid -1;
         }else if (nums[mid] < value){
             min = mid + 1;
         }
         if (min > max){
             return -1;
         }
     }
 }

点击查看更多排序算法
点击查看更多查找算法