初识java算法

引言：这是我对常用算法的初步理解，如有不足敬请指正，谢谢！

1.【选择排序法】
 初始数组   【63 4  24 1  3  15  】
 第一次排序 【4  24 1  3  15 】  63
 第二次排序 【4  1  3  15 】 24  63
 第三次排序 【4  1  3  】 15 24  63
 第四次排序 【1  3  】 4  15 24  63
 第五次排序 【1  】 3  4  15 24  63
 特点：每一次从待排序的数据中选出最小（或最大）的一个元素，顺序放到已经排好序的数列最后，直达全部排完！
 使用：如果数组有重复值，可选择该排序方法，因为遇到重复相等的值不会做任何处理，如果程序允许重复，该方法数据交换次数少，效率高！
   程序：
   private int[] array = new int[10];
   protected void do_button_actionPerformed() {
        // 创建随机数对象
        Random random = new Random();
        for (int i = 0; i < array.length; i++) {
        // 初始化数组元素,生成50以内的随机数
        array[i] = random.nextInt(50);   
        }
   }
   //核心算法  
   protected void do_button_1_actionPerformed() {
        int index;
        for (int i = 1; i < array.length; i++) {
            index = 0;
            for (int j = 1; j <= array.length - i; j++) {
                if (array[j] > array[index]) {
                    index = j;// 查找最大值
                }
            }
            // 交换在位置array.length-i和index(最大值)两个数
            int temp = array[array.length - i];
            array[array.length - i] = array[index];
            array[index] = temp;
         }
   }

2.【冒泡排序】
定义：基本思想是对比相邻的元素值，如果满足条件就交换元素，把较小的移动到前面，这样数组就像气泡一样从底部上升到顶部。
特点：比较的次数依排序轮数递减，因为每次都会确定一个最大值！
  程序：
  private int[] array = new int[10];  
  protected void do_button_actionPerformed(ActionEvent e) {
      Random random = new Random();
      for (int i = 0; i < array.length; i++) {
           array[i] = random.nextInt(50);
      }
  } 
  //核心算法  
  protected void do_button_1_actionPerformed(ActionEvent e) {
      for (int i = 1; i < array.length; i++) { // 长度为N的数组，循环轮数N-1，每次找出一个最大值
         // 比较相邻两个元素，较大的数往后冒泡
         for (int j = 0; j < array.length - i; j++) {
             if (array[j] > array[j + 1]) {
                  int temp = array[j];// 把第一个元素值保持到临时变量中
                  array[j] = array[j + 1];// 把第二个元素值保存到第一个元素单元中
                  array[j + 1] = temp;// 把临时变量也就是第一个元素原值保持到第二个元素中
              }    
            }
        }

3.【快速排序】
定义：对冒泡排序的一种改进，基本思想，通过一趟排序把要排序的数据分成2部分，其中一部分比参考数（通常选取每个部分的第1个数）小的，另一部分都是比参考数大的，对每个部分进行递归处理，直到每个部分只有一个元素即完成排序.
例子：
          初始数组：  49  38  65  97  76  13  27  49
        第一次排序： ｛27  38  13｝ 49｛76 97 65 49｝
    对左边序列排序： ｛13｝27｛38｝ 49｛76 97 65 49｝
        对右边排序：                ｛65 49｝76｛97｝
    对右边继续排序：                ｛49｝65
    完成排序的序列： ｛13｝27｛38｝49 49｝65 76｛97｝
核心算法：
    private int[] array = new int[10];
    protected void do_button_actionPerformed(ActionEvent e) {
        Random random = new Random();
        for (int i = 0; i < array.length; i++) {
            array[i] = random.nextInt(90);        
        }  
    } 
    //调用快速排序的方法，传入初始参数
    protected void do_button_1_actionPerformed(ActionEvent e) {
        quickSort(array, 0, array.length - 1);
    }
    //快速排序的逻辑排序相对复杂一些
    private void quickSort(int sortarray[], int lowIndex, int highIndex) {
        int lo = lowIndex;// 记录最小索引
        int hi = highIndex;// 记录最大索引
        int mid;// 记录分界点元素
        if (highIndex > lowIndex) {
            // 确定中间分界点元素值，sortarray[]数组
            mid = sortarray[(lowIndex + highIndex) / 2];
            while (lo <= hi) {
                while ((lo < highIndex) && (sortarray[lo] < mid))
                    ++lo;// 确定不大于分界元素值的最小索引
                while ((hi > lowIndex) && (sortarray[hi] > mid))
                    --hi;// 确定大于分界元素值的最大索引
                if (lo <= hi) {// 如果最小与最大索引没有重叠
                    swap(sortarray, lo, hi);// 交换两个索引的元素
                    ++lo;// 递增最小索引
                    --hi;// 递减最大索引
                }
            }
            if (lowIndex < hi)// 递归排序没有未分解元素
                quickSort(sortarray, lowIndex, hi);
            if (lo < highIndex)// 递归排序没有未分解元素
                quickSort(sortarray, lo, highIndex);
        }
    }  
    private void swap(int swapArray[], int i, int j) {
        // 交换数组元素
        int temp = swapArray[i];
        swapArray[i] = swapArray[j];
        swapArray[j] = temp;
    }
   
4.【直接插入排序】
定义： 将一个记录插入到有序数列中，使得到的新数列依然有序,插入一个新的元素会使得元素后面的数字向后移动一位.
      例子：2，8，7，5，9，6
      获取第一个元素：     2｛ 8，7，5，9，6｝
      依次插入后面的元素： 2，8｛ 7，5，9，6｝  
      依次插入后面的元素： 2，7，8｛ 5，9，6｝  
      依次插入后面的元素： 2，5，7，8｛ 9，6｝  
      依次插入后面的元素： 2，5，7，8 ，9｛6｝
      依次插入后面的元素： 2，5，6，7，8 ，9
核心算法：
    private int[] array = new int[10];   
    protected void do_button_actionPerformed(ActionEvent e) {
        Random random = new Random();
        for (int i = 0; i < array.length; i++) {
           array[i] = random.nextInt(90);
        }
    }
    protected void do_button_1_actionPerformed(ActionEvent e) {
        int tmp;// 定义临时变量
        int j;
        for (int i = 1; i < array.length; i++) {
           tmp = array[i];// 保存临时变量
           for (j = i - 1; j >= 0 && array[j] > tmp; j--) {
              array[j + 1] = array[j];// 数组元素交换
          }
           array[j + 1] = tmp;// 在排序位置插入数据
     }
  }