A: linear table

Includes: sequential storage structure and chain storage structure

1.1 Sequential Storage Structure

  • Advantages: High tail insertion efficiency and support random access.
  • Disadvantages: Low efficiency of intermediate insertion or deletion.
  • Applications: Array, ArrayList
  • Important apis: add(),remove()

Bubble sort

  • Application: the amount of data is small enough, such as bullfight card sorting

Multi-keyword sort

The principle of bubble sort algorithm is as follows:

  1. Compare adjacent elements. If the first one is bigger than the second, swap them both.
  2. Do the same for each pair of adjacent elements, starting with the first pair and ending with the last pair. At this point, the last element should be the largest number.
  3. Repeat this step for all elements except the last one.
  4. Keep repeating the above steps for fewer and fewer elements at a time until there are no more pairs to compare.
   public static void bubbleSort(int[] array){
        //3 1 5 8 2 9 4 6 7 n*(n-1)/2 n
      // The results of the first round of comparison: 1 3 5 2 8 4 6 7 9 the largest numbers sink to the lowest
        for(int i=array.length-1; i>0; i--) { boolean flag=true;
            for (int j = 0; j < i; j++) {
                if (array[j] > array[j + 1]) {
                    int temp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = temp;
                    flag=false; }}if(flag){
                break; }}}Copy the code

The average time complexity is O(n^2).

Selection sort

(to the first element as a benchmark, the subscript index fixed under the first element, the first cycle, in turn, compare with the first element and the element, if found smaller than the first element, the subscript index ran to the small number below, and then the data in the data comparison with the current index subscript, until the end of the first round to find the smallest element in an array, The subscript is fixed at the position of the smallest element, which then calls the position of the first element.

First, find the smallest (large) element in the unsorted sequence and store it at the beginning of the sorted sequence. Then, continue to find the smallest (large) element from the remaining unsorted elements and place it at the end of the sorted sequence. And so on until all the elements are sorted

int[] array=new int[]{3.2.5.8.1.9.4.6.7}

public static void selectSort(int[] array){
        for(int i=0; i<array.length-1; i++) { int index = i;for (int j = i+1; j < array.length; j++) {
                if(array[j] < array[index]) { index = j; }}/ /,2,5,8,3,9,4,6,7 {1};
            if(index! =i) {// If it is already minimal, there is no need to swapint temp = array[index]; array[index] = array[i]; array[i] = temp; }}}Copy the code

Chain storage structure

  • Application: LinkedList
  • Advantages: fast insertion and deletion speed, high memory utilization, no waste of memory size is not fixed, very flexible expansion.
  • Disadvantages: not random search, must start from the first traversal, search efficiency is low

Linked list application of mahjong sorting

public class Mahjong {
    public int suit;// I'm not sure what I'm doing
    public int rank;// Count one, two, three

    public Mahjong(int suit, int rank) {
        this.suit = suit;
        this.rank = rank;
    }

    @Override
    public String toString() {
        return "("+this.suit+""+this.rank+")"; }}Copy the code
  @Test
    public void addition_isCorrect() throws Exception {
        LinkedList<Mahjong> list=new LinkedList<Mahjong>();
        list.add(new Mahjong(3.1));
        list.add(new Mahjong(2.3));
        list.add(new Mahjong(3.7));
        list.add(new Mahjong(1.1));
        list.add(new Mahjong(3.8));
        list.add(new Mahjong(2.2));
        list.add(new Mahjong(3.2));
        list.add(new Mahjong(1.3));
        list.add(new Mahjong(3.9));
        System.out.println(list);
        radixSort(list);
        System.out.println(list);
    }
    public static void radixSort(LinkedList<Mahjong> list){
        // Group the points first
        LinkedList[] rankList=new LinkedList[9];
        for (int i = 0; i < rankList.length; i++) {
            rankList[i]=new LinkedList();
        }
        // Put the data into the corresponding group one by one
        while(list.size()>0) {/ / a
            Mahjong m=list.remove();
            // Put it in groups with subscript = points minus 1
            rankList[m.rank-1].add(m);
        }
        // put 9 together
        for (int i = 0; i < rankList.length; i++) {
            list.addAll(rankList[i]);
        }

        // Group suits first
        LinkedList[] suitList=new LinkedList[3];
        for (int i = 0; i < suitList.length; i++) {
            suitList[i]=new LinkedList();
        }

        // Put the data into the corresponding group one by one
        while(list.size()>0) {/ / a
            Mahjong m=list.remove();
            // Put it in groups with subscript = points minus 1
            suitList[m.suit-1].add(m);
        }
        // Combine the three together
        for (int i = 0; i < suitList.length; i++) { list.addAll(suitList[i]); }}Copy the code