数据结构有必要复习下了

声明：本文是转载

数据结构有必要复习下了


以下是我写的一些算法的实现，请多指教：

import java.util.Arrays;

public class 常用算法实现 {
    /**
     * 数据交换的方法
     * @param v
     * @param i
     * @param j
     */
    public static void swap(int[] v, int i, int j) {
        int temp = v[i];
        v[i] = v[j];
        v[j] = temp;
    }
   
   
    /**
     * 冒泡排序
     *
     * 使用场景：对已经经过初步排序的数据使用比较好
     *
     * 原理：扫描数据交换数据位置 对当前还未排好序的范围内的全部结点， 自上而下对相邻的两个结点依次进行比较和调整，
     * 让键值大的结点往下沉，键值小的结点往上冒。 即，每当两相邻比较后发现它们的排列顺序与排序要求相反时，就将它们互换。
     *
     * 时间复杂度：n的平方 空间复杂度：1
     *
     * 在冒泡排序中的核心部分是 for(i=0;i<n-1;i++) for(j=0;j<n-1-i;j++) if(a[j+1]<a[j])
     * swap(a[j],a[j+1]);
     */
    public static void bubbleUp(int list[]) {
        System.out.println("初始字符串:" + Arrays.toString(list));
        for (int i = 0; i < list.length - 1; i++) {
            boolean flag = false;
            for (int j = 0; j < list.length - i - 1; j++) {
                if (list[j] < list[j + 1]) {
                    swap(list,j,j+1);
                    flag = true;
                }
            }
            if (!flag) {
                break;
            }
            System.out.println("第" + (i + 1) + "次排列:" + Arrays.toString(list));
        }
        System.out.println("最终排列结果:" + Arrays.toString(list));
    }

    /**
     * 选择排序算法
     *
     * 试用场景：数据量比较少的情况下可以使用
     *
     * 原理：这是一个比较简单的算法，他的原理是，首先找到最小的数据 和第一个数据交换，然后再 找到次小的数据和第二个交换，以此类推.直到将数据排列好为止
     *
     * 时间复杂度： 2的n次方
     *
     * 空间复杂度:1
     *
     * @param args
     */
    public static void selectSort(int list[]) {
        System.out.println("初始字符串:" + Arrays.toString(list));
        for (int i = 0; i < list.length - 1; i++) {
            int min = list[i];
            for (int j = i + 1; j < list.length; j++) {
                if (min > list[j]) {
                    min = list[j];
                    swap(list,j,i);

                }
            }
            System.out.println("第" + (i + 1) + "次排列:" + Arrays.toString(list));
        }
        System.out.println("最终排列结果:" + Arrays.toString(list));
    }

    /**
     * 插入排序法 试用场景：数据量比较少的情况下 原理：是一种简单直观的排序算法; 从后到前在已排序数据中找到合适的位置插入进去
     * 初始可认为第一个数据已排序
     *
     * 时间复杂度：n的平方 空间复杂度: n
     *
     * @param args
     */
    public static void insertSort(int list[]) {
        System.out.println("初始字符串:" + Arrays.toString(list));
        // 注意：我们可认为第一个数据已排序，所以i是从1开始的
        for (int i = 1; i < list.length; i++) {
            int temp = list[i];
            int j = i;
            while (j > 0 && list[j] < list[j - 1]) {
                list[j] = list[j - 1];
                j--;
            }
            list[j] = temp;
            System.out.println("第" + i + "次排列:" + Arrays.toString(list));
        }
        System.out.println("最终排列结果:" + Arrays.toString(list));
    }

    /**
     * 快速排序算法
     *
     * 试用场景：数据量比较大的地方,如果有大量重复数据就比较麻烦
     *
     * 原理：首先检查待排序数组，如果<2个 直接推出程序，如果有超过 两个的数据，就选择一个分割点，将数据分成两个部分，小于分割点的分
     * 到一组，大于分割点的放到一组，然后对两组数据进行排序
     *
     * 时间复杂度：快速排序 O(n log n) 空间复杂度：1 splitIndex 划分数据的界限 items 最后字符的位置
     *
     * @param args
     */
    public static void quickSort(int list[], int startIndex, int items) {
        int j, last;
        /* 若数组包含的元素个数少于两个 */
        if (startIndex >= items)
        return;
        swap(list, startIndex, (startIndex + items) / 2); /* 将划分子集的元素移动到V[0] */
        last = startIndex; /* 用last记录中比关键字小间的最右位置 */
        for (j = startIndex + 1; j <= items; j++) /* 划分子集 */
        {
            if (list[j] < list[startIndex]) {
                swap(list, ++last, j);
            }
        }
        quickSort(list, startIndex, items - 1);
        quickSort(list, startIndex + 1, items);
    }

    public static void main(String args[]) {
        int list[] = { 800, 20, 70, 90, 50, 500, 400, 100, 850, 999, 1000, 0,-400 };
         bubbleUp(list);
         selectSort(list);
         insertSort(list);

    }
}