Qi

平衡树，子节点数目可以达到4个

特点

1. 若父节点中存有1个数据项，则必有2个子节点。

2. 若父节点中存有2个数据项，则必有3个子节点。

3. 若父节点中存有3个数据项，则必有4个子节点。

构造

插入数据：

• 未满节点直接插入

• 满节点 ABC 分裂 A不变 B到父节点 C到右侧

代码实现

class Node
{
private static final int ORDER = 4;
private int numItems;//节点中实际存储的数据项数目，其值一定不大于3
private Node parent;
private Node childArray[] = new Node[ORDER];//子节点数组
private DataItem itemArray[] = new DataItem[ORDER-1];//存储数据项数组
//-------------------------------------------------------------
// 把参数中的节点作为子节点，与当前节点进行连接
public void connectChild(int childNum, Node child)
   {
   childArray[childNum] = child;
   if(child != null)
      child.parent = this;//当前节点作为父节点
   }
//-------------------------------------------------------------
// 断开参数确定的节点与当前节点的连接，这个节点一定是当前节点的子节点。
public Node disconnectChild(int childNum)
   {
   Node tempNode = childArray[childNum];
   childArray[childNum] = null; //断开连接
   return tempNode;//返回要这个子节点
   }
//-------------------------------------------------------------
public Node getChild(int childNum)//获取相应的子节点
   { return childArray[childNum]; }
//-------------------------------------------------------------
public Node getParent()//获取父节点
   { return parent; }
//-------------------------------------------------------------
public boolean isLeaf()//是否是叶结点
   { return (childArray[0]==null) ? true : false; }//叶结点没有子节点
//-------------------------------------------------------------
public int getNumItems()//获取实际存储的数据项数目
  { return numItems; }
//-------------------------------------------------------------
public DataItem getItem(int index)   // 获取具体的数据项
   { return itemArray[index]; }
//-------------------------------------------------------------
public boolean isFull()//该节点是否已满
   { return (numItems==ORDER-1) ? true : false; }
//-------------------------------------------------------------
public int findItem(long key)       // 查找
   {                                    
   for(int j=0; j<ORDER-1; j++)         // 遍历数组
      {                                 
      if(itemArray[j] == null)          // 数组未满，未找到
         break;
      else if(itemArray[j].dData == key)
         return j;
      }
   return -1;
   }  // end findItem
//-------------------------------------------------------------
public int insertItem(DataItem newItem)//节点未满的插入
   {
   numItems++;                          
   long newKey = newItem.dData;         // 获得关键字
 
   for(int j=ORDER-2; j>=0; j--)        // 因为节点未满，所以从倒数第二项向前查找
      {                              
      if(itemArray[j] == null)          // 没存数据
         continue;                      
      else                              
         {                              
         long itsKey = itemArray[j].dData;//获得关键字
         if(newKey < itsKey)            //插入位置在其前面，但未必相邻
            itemArray[j+1] = itemArray[j]; //当前数据项后移
         else
            {
            itemArray[j+1] = newItem;   // 在其后位置插入
            return j+1;                 // 返回插入的位置下标
            }                           //    new item
         }  // end else (not null)
      }  // end for                     // shifted all items,
   //若上述代码没有执行返回操作，那么这是空节点（只有初始时根是这个情况）
   itemArray[0] = newItem;              // insert new item
   return 0;
   }  // end insertItem()
//-------------------------------------------------------------
public DataItem removeItem()        // 移除数据项，从后向前移除
   {
   // 假设节点非空
   DataItem temp = itemArray[numItems-1];  // 要移除的数据项
   itemArray[numItems-1] = null;           // 移除
   numItems--;                             // 数据项数目减一
   return temp;                            // 返回要移除的数据项
   }
//-------------------------------------------------------------
public void displayNode()           // format "/24/56/74/"
   {
   for(int j=0; j<numItems; j++)
      itemArray[j].displayItem();   // "/56"
   System.out.println("/");         // final "/"
   }
//-------------------------------------------------------------
}  // end class Node
////////////////////////////////////////////////////////////////


class Tree234
{
private Node root = new Node();            // 创建树的根
//-------------------------------------------------------------
//获取查找的下一个节点
public Node getNextChild(Node theNode, long theValue)
{
int j;
// 假设这个节点不是叶结点
int numItems = theNode.getNumItems();//获得当前节点的数据项数目
for(j=0; j<numItems; j++)          
   {                             
   if( theValue < theNode.getItem(j).dData )
      return theNode.getChild(j);  // 返回相应的节点
   }  // end for                   
return theNode.getChild(j);        // 此时j=numItems
}
//-------------------------------------------------------------
public int find(long key)
   {
   Node curNode = root;
   int childNumber;
   while(true)
      {
      if(( childNumber=curNode.findItem(key) ) != -1)//每次循环这句一定执行
         return childNumber;               // found it
      else if( curNode.isLeaf() )//叶结点上也没找到
         return -1;                        // can't find it
      else                                 // 不是叶结点，则继续向下查找
         curNode = getNextChild(curNode, key);
      }  // end while
   }
//-------------------------------------------------------------
// 插入数据项
public void insert(long dValue)
   {
   Node curNode = root;//当前节点标志
   DataItem tempItem = new DataItem(dValue);//插入数据项封装
 
   while(true)
      {
      if( curNode.isFull() )               // 是满节点
         {
         split(curNode);                   // 分裂
         curNode = curNode.getParent();    // 回到分裂出的父节点上
                                           // 继续向下查找
         curNode = getNextChild(curNode, dValue);
         }  // end if(node is full)
//后面的操作中节点都未满，否则先执行上面的代码
      else if( curNode.isLeaf() )          // 是叶结点，非满
         break;                            // 跳出，直接插入
   
      else
         curNode = getNextChild(curNode, dValue);//向下查找
      }  // end while
 
   curNode.insertItem(tempItem);       // 此时节点一定不满，直接插入数据项，
   }  // end insert()
//-------------------------------------------------------------
public void split(Node thisNode)     // 分裂
   {
   // 操作中节点一定是满节点，否则不会执行该操作
   DataItem itemB, itemC;
   Node parent, child2, child3;
   int itemIndex;
 
   itemC = thisNode.removeItem();    // 移除最右边的两个数据项，并保存为B和C
   itemB = thisNode.removeItem();    // 
   child2 = thisNode.disconnectChild(2); // //断开最右边两个子节点的链接
   child3 = thisNode.disconnectChild(3); // 
 
   Node newRight = new Node();       //新建一个节点，作为当前节点的兄弟节点
 
   if(thisNode==root)                // 是根
      {
      root = new Node();                // 新建一个根
      parent = root;                    // 把新根设为父节点
      root.connectChild(0, thisNode);   // 连接父节点和子节点
      }
   else                              // 不是根
      parent = thisNode.getParent();    // 获取父节点
 
  
   itemIndex = parent.insertItem(itemB); // 把B插入父节点中，返回插入位置
   int n = parent.getNumItems();         // 获得总数据项数目
 
   for(int j=n-1; j>itemIndex; j--)          //从后向前移除
      {                                    
      Node temp = parent.disconnectChild(j); // 断开连接
      parent.connectChild(j+1, temp);        // 连接到新的位置
      }
                           
   parent.connectChild(itemIndex+1, newRight);//连接到新位置
 
   // 处理兄弟节点
   newRight.insertItem(itemC);       // 将C放入兄弟节点中
   newRight.connectChild(0, child2); // 把子节点中最右边的两个连接到兄弟节点上
   newRight.connectChild(1, child3); //
   }  // end split()
//-------------------------------------------------------------
// gets appropriate child of node during search for value
 
public void displayTree()
   {
   recDisplayTree(root, 0, 0);
   }
//-------------------------------------------------------------
private void recDisplayTree(Node thisNode, int level,
                                           int childNumber)
   {
   System.out.print("level="+level+" child="+childNumber+" ");
   thisNode.displayNode();               // display this node
 
   // call ourselves for each child of this node
   int numItems = thisNode.getNumItems();
   for(int j=0; j<numItems+1; j++)
      {
      Node nextNode = thisNode.getChild(j);
      if(nextNode != null)
         recDisplayTree(nextNode, level+1, j);
      else
         return;
      }
   }  // end recDisplayTree()
//-------------------------------------------------------------\
}  // end class Tree234
////////////////////////////////////////////////////////////////


import java.io.*;
 
class Tree234App
{
public static void main(String[] args) throws IOException
   {
   long value;
   Tree234 theTree = new Tree234();
 
   theTree.insert(50);
   theTree.insert(40);
   theTree.insert(60);
   theTree.insert(30);
   theTree.insert(70);
 
   while(true)
      {
      System.out.print("Enter first letter of ");
      System.out.print("show, insert, or find: ");
      char choice = getChar();
      switch(choice)
         {
         case 's':
            theTree.displayTree();
            break;
         case 'i':
            System.out.print("Enter value to insert: ");
            value = getInt();
            theTree.insert(value);
            break;
         case 'f':
            System.out.print("Enter value to find: ");
            value = getInt();
            int found = theTree.find(value);
            if(found != -1)
               System.out.println("Found "+value);
            else
               System.out.println("Could not find "+value);
            break;
         default:
            System.out.print("Invalid entry\n");
         }  // end switch
      }  // end while
   }  // end main()
//--------------------------------------------------------------
public static String getString() throws IOException
   {
   InputStreamReader isr = new InputStreamReader(System.in);
   BufferedReader br = new BufferedReader(isr);
   String s = br.readLine();
   return s;
   }
//--------------------------------------------------------------
public static char getChar() throws IOException
   {
   String s = getString();
   return s.charAt(0);
   }
 
//-------------------------------------------------------------
public static int getInt() throws IOException
   {
   String s = getString();
   return Integer.parseInt(s);
   }
//-------------------------------------------------------------
}  // end class Tree234App
////////////////////////////////////////////////////////////////

选择排序（Selection Sort）是一种简单直观的排序算法，它在每一轮中选择未排序部分中的最小（或最大）元素，并将其放置在已排序部分的末尾。以下是一个选择排序的Java代码示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

import java.util.Arrays;

public class SelectionSort {

    public static void selectionSort(int[] arr) {
        int n = arr.length;

        for (int i = 0; i < n - 1; i++) {
            int minIndex = i;

            // 找到未排序部分的最小值索引
            for (int j = i + 1; j < n; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }

            // 将最小值与未排序部分的第一个元素交换
            int temp = arr[minIndex];
            arr[minIndex] = arr[i];
            arr[i] = temp;
        }
    }

    public static void main(String[] args) {
        int[] arr = {64, 25, 12, 22, 11};
        System.out.println("Original array: " + Arrays.toString(arr));

        selectionSort(arr);

        System.out.println("Sorted array: " + Arrays.toString(arr));
    }
}

在这个示例中，selectionSort 方法使用选择排序算法对整数数组进行排序。它从未排序部分中选择最小值，并将其与未排序部分的第一个元素交换。通过多次迭代，每次选择一个最小值，最终数组会变得有序。

尽管选择排序的时间复杂度较高（O(n^2)），但它在简单场景中具有一定的实用性。

计数排序（Counting Sort）是一种非比较性的排序算法，适用于待排序数组中元素的范围比较小的情况。以下是一个计数排序的Java代码示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

import java.util.Arrays;

public class CountingSort {

    public static void countingSort(int[] arr) {
        int n = arr.length;

        // 找到数组中的最大值和最小值
        int max = Arrays.stream(arr).max().getAsInt();
        int min = Arrays.stream(arr).min().getAsInt();

        // 创建计数数组，大小为最大值和最小值之差加1
        int range = max - min + 1;
        int[] countArray = new int[range];

        // 统计每个元素出现的次数
        for (int i = 0; i < n; i++) {
            countArray[arr[i] - min]++;
        }

        // 根据计数数组重新构造排序后的数组
        int index = 0;
        for (int i = 0; i < range; i++) {
            while (countArray[i] > 0) {
                arr[index++] = i + min;
                countArray[i]--;
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = {4, 2, 2, 8, 3, 3, 1};
        System.out.println("Original array: " + Arrays.toString(arr));

        countingSort(arr);

        System.out.println("Sorted array: " + Arrays.toString(arr));
    }
}

在这个示例中，countingSort 方法使用计数排序算法对整数数组进行排序。它首先找到数组中的最大值和最小值，然后创建一个计数数组来统计每个元素出现的次数。最后，根据计数数组重新构造排序后的数组。

请注意，计数排序适用于元素范围较小的情况，因为它的性能与元素范围有关。

桶排序（Bucket Sort）是一种排序算法，它将输入数据分割成若干个桶（区间范围），然后对每个桶中的数据进行排序，最后将各个桶中的数据合并起来。以下是一个桶排序的Java代码示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class BucketSort {

    public static void bucketSort(double[] arr) {
        int n = arr.length;
        List<Double>[] buckets = new ArrayList[n];

        // 初始化桶
        for (int i = 0; i < n; i++) {
            buckets[i] = new ArrayList<>();
        }

        // 将元素放入对应的桶中
        for (int i = 0; i < n; i++) {
            int bucketIndex = (int) (n * arr[i]);
            buckets[bucketIndex].add(arr[i]);
        }

        // 对每个桶中的元素进行排序
        for (int i = 0; i < n; i++) {
            Collections.sort(buckets[i]);
        }

        // 将排序后的桶合并成一个有序数组
        int index = 0;
        for (int i = 0; i < n; i++) {
            for (double value : buckets[i]) {
                arr[index++] = value;
            }
        }
    }

    public static void main(String[] args) {
        double[] arr = {0.42, 0.32, 0.33, 0.52, 0.37, 0.47, 0.51};
        System.out.println("Original array: " + Arrays.toString(arr));

        bucketSort(arr);

        System.out.println("Sorted array: " + Arrays.toString(arr));
    }
}

在这个示例中，bucketSort 方法使用桶排序算法对一个小数数组进行排序。它首先将元素按照一定的规则放入不同的桶中，然后对每个桶中的元素进行排序，最后将排序后的桶合并成一个有序数组。

注意，这个示例中的桶排序适用于小数排序，每个桶内部使用了简单的插入排序。实际应用中，桶的数量和分桶规则的选择会影响算法的性能。

拓扑排序是用于有向无环图（DAG）的一种排序方式，它可以用来表示依赖关系，任务调度等情况。下面是一个拓扑排序的Java代码示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

import java.util.*;

public class TopologicalSort {

    public static List<Integer> topologicalSort(int vertices, List<Integer>[] graph) {
        List<Integer> result = new ArrayList<>();
        int[] inDegree = new int[vertices];

        // 计算每个顶点的入度
        for (List<Integer> neighbors : graph) {
            for (int neighbor : neighbors) {
                inDegree[neighbor]++;
            }
        }

        // 将入度为0的顶点加入队列
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < vertices; i++) {
            if (inDegree[i] == 0) {
                queue.offer(i);
            }
        }

        // 逐步移除入度为0的顶点，并更新相关顶点的入度
        while (!queue.isEmpty()) {
            int vertex = queue.poll();
            result.add(vertex);

            for (int neighbor : graph[vertex]) {
                inDegree[neighbor]--;
                if (inDegree[neighbor] == 0) {
                    queue.offer(neighbor);
                }
            }
        }

        return result;
    }

    public static void main(String[] args) {
        int vertices = 6;
        List<Integer>[] graph = new ArrayList[vertices];
        for (int i = 0; i < vertices; i++) {
            graph[i] = new ArrayList<>();
        }

        graph[5].add(2);
        graph[5].add(0);
        graph[4].add(0);
        graph[4].add(1);
        graph[2].add(3);
        graph[3].add(1);

        List<Integer> result = topologicalSort(vertices, graph);
        System.out.println("Topological Sort: " + result);
    }
}

在这个示例中，topologicalSort 方法使用拓扑排序算法对给定的有向无环图（使用邻接表表示）进行排序。该算法的核心思想是从入度为0的顶点开始，逐步移除顶点并更新相关顶点的入度。

以下是快速排序的Java代码示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

import java.util.Arrays;

public class QuickSort {

    public static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            int pivotIndex = partition(arr, low, high);
            quickSort(arr, low, pivotIndex - 1);
            quickSort(arr, pivotIndex + 1, high);
        }
    }

    private static int partition(int[] arr, int low, int high) {
        int pivot = arr[high];
        int i = low - 1;

        for (int j = low; j < high; j++) {
            if (arr[j] < pivot) {
                i++;
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }

        int temp = arr[i + 1];
        arr[i + 1] = arr[high];
        arr[high] = temp;

        return i + 1;
    }

    public static void main(String[] args) {
        int[] arr = {10, 7, 8, 9, 1, 5};
        System.out.println("Original array: " + Arrays.toString(arr));

        int n = arr.length;
        quickSort(arr, 0, n - 1);

        System.out.println("Sorted array: " + Arrays.toString(arr));
    }
}

在这个示例中，quickSort 方法使用快速排序算法对整数数组进行排序。快速排序是一种分治算法，它选取一个基准元素，将数组分成两个部分，一个部分包含小于基准的元素，另一个部分包含大于基准的元素，然后递归地对两个部分进行排序。

下面是归并排序的Java代码示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59

import java.util.Arrays;

public class MergeSort {

    public static void mergeSort(int[] arr) {
        int n = arr.length;

        if (n <= 1) {
            return;
        }

        int mid = n / 2;
        int[] left = Arrays.copyOfRange(arr, 0, mid);
        int[] right = Arrays.copyOfRange(arr, mid, n);

        mergeSort(left);
        mergeSort(right);

        merge(arr, left, right);
    }

    private static void merge(int[] arr, int[] left, int[] right) {
        int leftLength = left.length;
        int rightLength = right.length;
        int i = 0, j = 0, k = 0;

        while (i < leftLength && j < rightLength) {
            if (left[i] <= right[j]) {
                arr[k] = left[i];
                i++;
            } else {
                arr[k] = right[j];
                j++;
            }
            k++;
        }

        while (i < leftLength) {
            arr[k] = left[i];
            i++;
            k++;
        }

        while (j < rightLength) {
            arr[k] = right[j];
            j++;
            k++;
        }
    }

    public static void main(String[] args) {
        int[] arr = {12, 11, 13, 5, 6, 7};
        System.out.println("Original array: " + Arrays.toString(arr));

        mergeSort(arr);

        System.out.println("Sorted array: " + Arrays.toString(arr));
    }
}

在这个示例中，mergeSort 方法使用归并排序算法对整数数组进行排序。归并排序是一种分治算法，它将数组逐步分割为更小的子数组，然后对子数组进行排序并合并，从而实现整个数组的排序。

以下是希尔排序的Java代码示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

import java.util.Arrays;

public class ShellSort {

    public static void shellSort(int[] arr) {
        int n = arr.length;

        // 初始步长设定为数组长度的一半，逐渐减小步长
        for (int gap = n / 2; gap > 0; gap /= 2) {
            for (int i = gap; i < n; i++) {
                int temp = arr[i];
                int j;

                // 在当前步长下，使用插入排序对子数组进行排序
                for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {
                    arr[j] = arr[j - gap];
                }

                arr[j] = temp;
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = {12, 34, 54, 2, 3};
        System.out.println("Original array: " + Arrays.toString(arr));

        shellSort(arr);

        System.out.println("Sorted array: " + Arrays.toString(arr));
    }
}

在这个示例中，shellSort 方法使用希尔排序算法对整数数组进行排序。希尔排序是一种插入排序的改进版本，它通过逐步缩小步长，将较大的元素尽快移到正确的位置，从而提高了插入排序的效率。

这只是一个基本的希尔排序示例，实际应用中可能需要考虑不同的步长序列和性能优化。希尔排序的步长序列选择会影响算法的性能。