算法初探

• • 1.排序
  • • 1.1冒泡排序
    • 1.2选择排序
    • 1.3插入排序
  • 2.查找
  • • 2.1线性查找
    • 2.2二分查找

1.排序

定义：对一组数据按照某种原则进行排序

1.1冒泡排序

思想：

类似于小鱼吐泡泡的过程，泡泡是一个一个逐渐增大的，而冒泡排序就是将一组数据最下（上）面的元素与其上（下）的元素一一比较从而实现一定的顺序。
图解：

算法代码：

        for (int i = 0; i < array.length; i++)
            for (int j = 0; j < array.length - 1 - i; j++)
                if (array[j + 1] < array[j]) {
                    int temp = array[j + 1];
                    array[j + 1] = array[j];
                    array[j] = temp;
                }

1.2选择排序

思想：
将一组数据中的一个数据的最后一个或第一个数据定为最大或者最小值（key），在将数组中的其他数值与其一一对比，若符合条件则交换，直到key的值最大或最小，此时放入对应位置。
图解;

算法代码：

        for (int i = 0; i < array.length; i++) {
            int minIndex = i;
            for (int j = i; j < array.length; j++) {
                if (array[j] < array[minIndex]) //找到最小的数
                    minIndex = j; //将最小数的索引保存
            }
            int temp = array[minIndex];
            array[minIndex] = array[i];
            array[i] = temp;
        }

1.3插入排序

思想：
一组数据中我们可以将数组分为有序和无序两个部分；例如（1，5，3，7，9，2），我们可以将“1”看成有序部分，后面则为无序部分，那么插入排序则是将无序部分的元素与有序部分相比较，大的放置在1的后面，小的则将1往后移动，为小的数字留出空间。
图解：

算法代码：

        int current;
        for (int i = 0; i < array.length - 1; i++) {
            current = array[i + 1];
            int preIndex = i;
            while (preIndex >= 0 && current < array[preIndex])
             {
                array[preIndex + 1] = array[preIndex];
                preIndex--;
            }
            array[preIndex + 1] = current;
        }

2.查找

定义：在一组数据中寻找自己想要的值

2.1线性查找

思想：
类似于找资料时，从书的第一页找到最后一页，效率低
算法代码：

public static void main(String[] args)
	{
		int[] arr = {1, 3, 9, 8, 7, -1, 2};
		int index = seqSearch(arr, 7);
		if(index == -1)
		System.out.println("没找到 " + 7);
		else
		System.out.println("下标为 " + index);
	}

2.2二分查找

思想：
在一个已经有序的数组中查找数据，例如（1，2，3，4，6，7，8，9）这一串数组中，我们会将最大下标和最小下标赋值给两个变量min ,max,查找会从（min+max）/2下标开始，大于指定值则max=（min+max）/2-1,否则
min=（min+max）/2+1；依次重复直至找到 或者 min>max退出。
图解：

算法代码：

package algorithm.search.binarysearch; 
import algorithm.sort.quickSort.QuickSort;
public class BinarySearch {
	public static int binarySearch(int[] nums,int key){
		int length=nums.length;
		QuickSort.quickSort(nums, 0, length-1);
		int min=0;
		int max=length-1;
		while(min<=end){
			int mid=(min+max)/2;
			int now=nums[mid];
			if(now==key){
				return mid;
			}
			if(now<key){
				min=mid+1;
			}
			if(now>key){
				max=mid-1;
			}			
		}				
		return -1;
	} 
}