关于Java算法与数据结构-队列的顺序存储实现

package com.ssm.cts.test;

/**
 * CopyRright (c)2018-2028: chanpinxue.cn 
 * Project: cts 
 * Module Name: QueueTest
 * Comments: 队列
 * JDK version used: JDK1.8 
 * Author: jzh 
 * Create Date: 2018-12-07
 * Modified By: jzh 
 * Modified Date: 2018-12-07
 * Why & What is modified:
 * Version: <1.0>
 */

// Queue接口
interface Queue {
  // 返回队列的大小
  public int getSize();

  // 判断队列是否为空
  public boolean isEmpty();

  // 数据元素e入队
  public void add(Object e);

  // 队首元素出队
  public Object poll() throws QueueEmptyException;

  // 取队首元素
  public Object peek() throws QueueEmptyException;
}

// QueueEmptyException队列为空时出队或取队首元素抛出此异常
@SuppressWarnings("serial")
class QueueEmptyException extends RuntimeException {
  public QueueEmptyException(String err) {
    super(err);
  }
}

// Queue的顺序存储实现
class QueueArray implements Queue {
  //private static final int LEN = 9;// 队列默认大小
  public Object[] elements; // 数据元素数组
  private int capacity; // 数组的大小elements.length
  private int front; // 队首指针,指向队首
  private int rear; // 队尾指针,指向队尾后一个位置
  
  public QueueArray(int LEN) {
    capacity = LEN + 1;
    elements = new Object[capacity];
    front = rear = 0;
  }

    // 返回队列的大小
  public int getSize() {
    return (rear - front + capacity) % capacity;
  }

    // 判断队列是否为空
  public boolean isEmpty() {
    return front == rear;
  }

    // 数据元素e入队
  public void add(Object e) {
    if (getSize() == capacity - 1)
      expandSpace();
    elements[rear] = e;
    rear = (rear + 1) % capacity;
  }

  private void expandSpace() {
    Object[] a = new Object[elements.length * 2];
    int i = front;
    int j = 0;
    
    // 将从front开始到rear前一个存储单元的元素复制到新数组
    while (i != rear) {
      a[j++] = elements[i];
      i = (i + 1) % capacity;
    }
    elements = a;
    capacity = elements.length;
    front = 0;
    rear = j; // 设置新的队首、队尾指针
  }

    // 队首元素出队
  public Object poll() throws QueueEmptyException {
    if (isEmpty()) {
      throw new QueueEmptyException("错误:队列为空");
    }
    
    Object obj = elements[front];
    elements[front] = null;
    front = (front + 1) % capacity;
    return obj;
  }

    // 取队首元素
  public Object peek() throws QueueEmptyException {
    if (isEmpty())
      throw new QueueEmptyException("错误:队列为空");
    return elements[front];
  }
}

public class QueueTest {
  // 测试
  public static void main(String[] args) {
    QueueArray queue = new QueueArray(9);
    queue.add("j");
    queue.add("z");
    queue.add("h");
    
    System.out.println("队列长度:" + queue.getSize());
    
    // 使用 for 循环数组
    for (Object obj  : queue.elements) {
      if (obj != null) {
        System.out.print(obj + " ");
      }
    }
    
    // 使用 foreach 循环数组
    for (int i = 0; i < queue.getSize(); i++) {
        System.out.print(queue.elements[i] + " ");
    }
    
    System.out.println();
    
    // 队首元素出队
    Object o = queue.poll();
    System.out.println(o);
    
    System.out.println("队列长度:" + queue.getSize());

  }

}

关于Java算法与数据结构-单向链表

package com.ssm.cts.test;

/**
 * CopyRright (c)2018-2028: chanpinxue.cn 
 * Project: cts 
 * Module Name: SLTest
 * Comments: 单向链表
 * JDK version used: JDK1.8 
 * Author: jzh 
 * Create Date: 2018-12-04
 * Modified By: jzh 
 * Modified Date: 2018-12-04
 * Why & What is modified:
 * Version: <1.0>
 */

// 定义节点结构
class NodeData {
  String key; // 结点的关键字
  String name;
  int age;
}

// 定义链表结构
class SLNode {
  NodeData nodeData = new NodeData();
  SLNode nextNode;

  // 追加结点
  @SuppressWarnings({ "null", "unused" })
  SLNode addEnd(SLNode head, NodeData nodeData) {
    SLNode temp;
    SLNode node = new SLNode();
    node.nodeData = nodeData; // 保存数据
    node.nextNode = null; // 设置结点指针为空,即为表尾
    // 头指针
    if (head == null) {
      head = node;
      return head;
    }
    temp = head;
    // 查找链表的末尾
    while (temp.nextNode != null) {
      temp = temp.nextNode;
    }
    temp.nextNode = node;
    return head;
  }

  @SuppressWarnings({ "null", "unused" })
  SLNode addFirst(SLNode head, NodeData nodeData) {
    SLNode node = new SLNode();
    node.nodeData = nodeData; // 保存数据
    node.nextNode = head; // 指向头指针所指结点
    head = node; // 头指针指向新增结点
    return head;
  }

  // 查找结点
  SLNode findNode(SLNode head, String key) {
    SLNode temp;
    temp = head; // 保存链表头指针
    // 若结点有效,则进行查找
    while (temp != null) {
      // 若结点关键字与传入关键字相同
      if (temp.nodeData.key.compareTo(key) == 0) {
        return temp; // 返回该结点指针
      }
      temp = temp.nextNode; // 处理下一结点
    }
    return null; // 返回空指针
  }

  // 插入结点
  @SuppressWarnings({ "null", "unused" })
  SLNode insertNode(SLNode head, String findkey, NodeData nodeData) {
    SLNode node, temp;
    node = new SLNode();
    node.nodeData = nodeData; // 保存结点中的数据
    temp = findNode(head, findkey);
    // 若找到要插入的结点
    if (temp != null) {
      node.nextNode = temp.nextNode; // 新插入结点指向关键结点的下一结点
      temp.nextNode = node; // 设置关键结点指向新插入结点
    } else {
      System.out.print("未找到正确的插入位置!\n"); // 释放内存
    }
    return head; // 返回头指针
  }

  int deleteNode(SLNode head, String key) {
    SLNode node, temp; // node保存删除结点的前一结点
    temp = head;
    node = head;
    while (temp != null) {
      // 找到关键字,执行删除操作
      if (temp.nodeData.key.compareTo(key) == 0) {
        node.nextNode = temp.nextNode; // 使前一结点指向当前结点的下一结点
        return 1;
      } else {
        node = temp; // 指向当前结点
        temp = temp.nextNode; // 指向下一结点
      }
    }
    return 0; // 未删除
  }

  // 计算链表长度
  int getLength(SLNode head) {
    SLNode temp;
    int Len = 0;
    temp = head;
    // 遍历整个链表
    while (temp != null) {
      Len++; // 累加结点数量
      temp = temp.nextNode; // 处理下一结点
    }
    return Len; // 返回结点数量
  }

  // 遍历链表
  void getAllNode(SLNode head) {
    SLNode temp;
    NodeData nodeData;
    temp = head;
    System.out.printf("当前链表共有%d个结点。链表所有数据如下:\n", getLength(head));
    // 循环处理链表每个结点
    while (temp != null) {
      nodeData = temp.nodeData; // 获取结点数据
      System.out.printf("结点(%s,%s,%d)\n", nodeData.key, nodeData.name, nodeData.age);
      temp = temp.nextNode; // 处理下一结点
    }
  }

}

public class SLTest {

  // 测试
  public static void main(String[] args) {
    SLNode node, head = null;
    SLNode sl = new SLNode();

    for (int i = 0; i <= 5; i++) {
      NodeData nodeData = new NodeData();
      nodeData.key = String.valueOf(i);
      nodeData.name = "jzh" + String.valueOf(i);
      nodeData.age = 20 + i;
      head = sl.addEnd(head, nodeData); // 在链表尾部添加结点
    }

    sl.getAllNode(head); // 显示所有结点

    NodeData nodeData = new NodeData();
    nodeData.key = "99";
    nodeData.name = "chanpinxue.cn";
    nodeData.age = 10; // 输入插入结点数据
    head = sl.insertNode(head, "2", nodeData); // 调用插入函数
    sl.getAllNode(head); // 显示所有结点

    sl.deleteNode(head, "3"); // 调用删除结点函数

    node = sl.findNode(head, "4"); // 调用查找函数,返回结点指针
    // 若返回结点指针有效
    if (node != null) {
      nodeData = node.nodeData; // 获取结点的数据
      System.out.printf("关键字4的结点信息为(%s,%s,%d)\n", nodeData.key, nodeData.name, nodeData.age);
    }

  }

}

关于Java算法与数据结构-栈的链式存储实现

package com.ssm.cts.test;

/**
 * CopyRright (c)2018-2028: chanpinxue.cn 
 * Project: cts 
 * Module Name: StackTest
 * Comments: 栈
 * JDK version used: JDK1.8 
 * Author: jzh 
 * Create Date: 2018-12-04
 * Modified By: jzh 
 * Modified Date: 2018-12-04
 * Why & What is modified:
 * Version: <1.0>
 */
public class StackTest {

  // 测试
  public static void main(String[] args) {
        // No enclosing instance of type StackTest is accessible. 
        // Must qualify the allocation with an enclosing instance of type StackTest (e.g. x.new A() where x is an instance of StackTest).
        StackTest test = new StackTest();
        StackSLinked stackSLinked = test.new StackSLinked();
        stackSLinked.push(11);
        stackSLinked.push(22);
        stackSLinked.push(33);
        stackSLinked.push(55);
        stackSLinked.push(66);
        stackSLinked.push(77);
        
        // 打印
        display("栈的链式存储实现-栈内元素:", stackSLinked.top);

        // 栈顶出栈
        stackSLinked.pop();

        // 打印
        display("栈的链式存储实现-栈内元素:", stackSLinked.top);
        
  }
  
  // 显示
  public static void display(String str, SLNode node) {
    System.out.println(str);
    while (node != null) {
      System.out.print(node.getData() + " ");
      node = node.next;
    }
    System.out.println();
  }
  
  // 栈基本功能接口
  public interface Stack {
    // 返回堆栈的大小
    public int getSize();

    // 判断堆栈是否为空
    public boolean isEmpty();

    // 数据元素e入栈
    public void push(Object e);

    // 栈顶元素出栈
    public Object pop() throws StackEmptyException;

    // 取栈顶元素
    public Object peek() throws StackEmptyException;
  }

  @SuppressWarnings("serial")
  public class StackEmptyException extends RuntimeException {
    public StackEmptyException(String err) {
      super(err);
    }
  }
  
  public interface Node {
    // 获取结点数据域
    public Object getData();

    // 设置结点数据域
    public void setData(Object obj);
  }
  
  public class SLNode implements Node {
    private Object element;
    private SLNode next;

    public SLNode() {
      this(null, null);
    }

    public SLNode(Object ele, SLNode next) {
      this.element = ele;
      this.next = next;
    }

    public SLNode getNext() {
      return next;
    }

    public void setNext(SLNode next) {
      this.next = next;
    }

    /**************** Methods of Node Interface **************/
    public Object getData() {
      return element;
    }

    public void setData(Object obj) {
      element = obj;
    }
  }

  // 栈的链式存储实现
  public class StackSLinked implements Stack {
    private SLNode top; // 链表首结点引用
    private int size; // 栈的大小

    public StackSLinked() {
      top = null;
      size = 0;
    }

    // 返回堆栈的大小
    public int getSize() {
      return size;
    }

    // 判断堆栈是否为空
    public boolean isEmpty() {
      return size == 0;
    }

    // 数据元素e入栈
    public void push(Object e) {
      SLNode q = new SLNode(e, top);
      top = q;
      size++;
    }

    // 栈顶元素出栈
    public Object pop() throws StackEmptyException {
      if (size < 1)
        throw new StackEmptyException("错误,堆栈为空。");
      Object obj = top.getData();
      top = top.getNext();
      size--;
      return obj;
    }

    // 取栈顶元素
    public Object peek() throws StackEmptyException {
      if (size < 1)
        throw new StackEmptyException("错误,堆栈为空。");
      return top.getData();
    }
  }

}
阅读全文

关于Java算法与数据结构-栈的顺序存储实现

package com.ssm.cts.test;

/**
 * CopyRright (c)2018-2028: chanpinxue.cn 
 * Project: cts 
 * Module Name: StackTest
 * Comments: 栈
 * JDK version used: JDK1.8 
 * Author: jzh 
 * Create Date: 2018-12-04
 * Modified By: jzh 
 * Modified Date: 2018-12-04
 * Why & What is modified:
 * Version: <1.0>
 */
public class StackTest {

  // 测试
  public static void main(String[] args) {
    // No enclosing instance of type StackTest is accessible. 
    // Must qualify the allocation with an enclosing instance of type StackTest (e.g. x.new A() where x is an instance of StackTest).
    StackTest test = new StackTest();
    StackArray stack = test.new StackArray(9);
        stack.push(1);
        stack.push(2);
        stack.push(3);
        stack.push(5);
        stack.push(6);
        stack.push(7);
        
        // 打印
        display("栈内元素:", stack);

        int top = (int) stack.peek();
        System.out.println("栈顶: " + top);

        // 栈顶出栈
        stack.pop();

        // 打印
        display("栈内元素:", stack);
  }
  
  // 显示
  public static void display(String str, StackArray stack) {
    System.out.println(str);
    for (int i = stack.getSize() - 1; i >= 0; i--) {
      System.out.print(stack.elements[i].toString() + ' ');
    }
    System.out.println();
  }
  
  // 栈基本功能接口
  public interface Stack {
    // 返回堆栈的大小
    public int getSize();

    // 判断堆栈是否为空
    public boolean isEmpty();

    // 数据元素e入栈
    public void push(Object e);

    // 栈顶元素出栈
    public Object pop() throws StackEmptyException;

    // 取栈顶元素
    public Object peek() throws StackEmptyException;
  }

  @SuppressWarnings("serial")
  public class StackEmptyException extends RuntimeException {
    public StackEmptyException(String err) {
      super(err);
    }
  }
  
  // 栈顺序存储实现
  public class StackArray implements Stack {
    //private final int LEN = 9; //数组的默认大小
    private Object[] elements; // 数据元素数组
    private int top; // 栈顶指针

    public StackArray(int LEN) {
      top = -1;
      elements = new Object[LEN];
    }

    // 返回堆栈的大小
    public int getSize() {
      return top + 1;
    }

    // 判断堆栈是否为空
    public boolean isEmpty() {
      return top < 0;
    }

    // 数据元素e入栈
    public void push(Object e) {
      if (getSize() >= elements.length)
        expandSpace();
      elements[++top] = e;
    }

    private void expandSpace() {
      Object[] a = new Object[elements.length * 2];
      for (int i = 0; i < elements.length; i++)
        a[i] = elements[i];
      elements = a;
    }

    // 栈顶元素出栈
    public Object pop() throws StackEmptyException {
      if (getSize() < 1)
        throw new StackEmptyException("错误,堆栈为空。");
      Object obj = elements[top];
      elements[top--] = null;
      return obj;
    }

    // 取栈顶元素
    public Object peek() throws StackEmptyException {
      if (getSize() < 1)
        throw new StackEmptyException("错误,堆栈为空。");
      return elements[top];
    }
  }

}

栈内元素:
7 6 5 3 2 1
栈顶: 7
栈内元素:
6 5 3 2 1 阅读全文

关于Java排序算法-归并排序(Merge Sort)

二路归并排序的基本思想:设 n 个待排记录,看成是 n 个有序的子序列,每个子序列的长度为 1 ,对此进行两两归并,得到 n/2 个长度为 2 或 1 的有序子序列;再继续两两归并,得到 n/4 个有序子序列,重复进行直至得到一个长度为 n 的有序序列为止。

public class MergeSort {
  public static void main(String[] args) {
    //int[] arr = { 9, 8, 7, 6, 5, 4, 3, 2, 1 };
    int[] arr = { 21, 25, 49, 25, 93, 62, 72, 8, 37, 16, 54 };

    display("原始数据: ", arr);
    
    mainMerge(arr, arr.length);
    
    display("排序结果: ", arr);
  }

  // 显示
  public static void display(String str, int[] arr) {
    System.out.println(str);
    for (int i = 0; i < arr.length; i++) {
      System.out.print(arr[i] + " ");
    }
    System.out.println();
  }
  
  // 归并排序主算法:
  // 第一趟: arr归并到arrDest;
  // 第二趟: arrDest归并到arr; ......,需偶数趟。
  // 若最后一趟 len>=n,则arrDest直接复制到arr。
  public static void mainMerge(int[] arr, int n) {
    // 对数组arr[n]中的记录进行归并排序
    int[] arrDest = new int[n];
    int len = 1;
    while (len < n) {
      oneMerge(arr, arrDest, n, len);
      len *= 2;
      oneMerge(arrDest, arr, n, len);
      len *= 2;
    }
    // 清空临时数组
    arrDest = null;
  }

  // 一趟归并排序算法:把arr[n]中长度为len的有序表两两归并到arrDest[n]
  public static void oneMerge(int[] arr, int[] arrDest, int n, int len) {
    int p = 0; // 一对待合并表的第一个元素的位置
    
    // 循环两两归并
    while (p + 2 * len - 1 <= n - 1) {
      // twoMerge(int[] arr, int[] arrDest, int s, int m, int t)
      // 将有序表arr[s..m] 和  arr[m+1..t] 归并为有序表arrDest[s..t]
      twoMerge(arr, arrDest, p, p + len - 1, p + 2 * len - 1);
      p += 2 * len;
    }
    
    if (p + len <= n - 1) {
      // 归并最后两个长度不等的有序表
      twoMerge(arr, arrDest, p, p + len - 1, n - 1);
    } else {
      // 复制最后剩下的一个有序表
      for (int i = p; i <= n - 1; i++) {
        arrDest[i] = arr[i];
      }
    }
  }

  // 二路归并算法:将有序表 arr[s..m] 和 arr[m+1..t] 归并为有序表arrDest[s..t]
  public static void twoMerge(int[] arr, int[] arrDest, int s, int m, int t) {
    int i, j, k;
    i = s;
    j = m + 1;
    k = s; // 分别指向每个表的起始位置
    
    // 两个有序表的归并
    while (i <= m && j <= t) {
      if (arr[i] <= arr[j]) {
        arrDest[k] = arr[i];
        i++;
        k++;
      } else {
        arrDest[k] = arr[j];
        j++;
        k++;
      }
    }
    
    // 复制第一个有序表中未归并的元素
    while (i <= m) {
      arrDest[k] = arr[i];
      i++;
      k++;
    }
    
    // 复制第二个有序表中未归并的元素
    while (j <= t) {
      arrDest[k] = arr[j];
      j++;
      k++;
    }
  }

}
阅读全文

关于Java排序算法-堆排序(Heap Sort)

堆排序是利用堆的特性进行排序的过程。
堆排序:输出堆顶的最小(大)值后,使剩余的n-1个元素序列重新再建成堆,则可得到原序列的次小(大)值。反复进行可得到一个有序序列,整个过程称为堆排序。
堆排序分为两个步骤:
根据初始输入数据,形成初始堆;
通过一系列的记录交换和重新调整堆进行排序。

public class HeapSort {
  
  // 主函数
  public static void main(String[] args) {
    int[] arr = { 27, 83, 96, 38, 11, 9 };
    sort(arr);
  }
  
  // 排序
  public static void sort(int[] arr) {
    // arr为待排序表, n为表的长度
    int n = arr.length;
    
    display("原始数据 : ", arr);
    
    // 建堆函数:根据堆的定义,从最后一个非终端结点(第(n-2)/2个)开始筛选,直至到根结点为止。这一过程使得初始序列 arr[0..n-1] 建成一个堆。
    // 构建大顶堆
    for (int i = (n - 2) / 2; i >= 0; i--) {
      adjustHeap(arr, i, n);
      display("构建中: ", arr);
    }
    
    display("大顶堆 : ", arr);
    
    // 调整堆结构
    // 交换堆顶元素与末尾元素
    for (int j = n - 1; j > 0; j--) {
      // 将堆顶元素与末尾元素进行交换
      swap(arr, 0, j);
      // 重新对堆进行调整
      adjustHeap(arr, 0, j);
      display("排序中: ", arr);
    }
    
    display("排序结果: ", arr);
  }
  
  // 调整大顶堆
  public static void adjustHeap(int[] arr, int i, int length) {
    // 先取出当前元素i
    int temp = arr[i];
    
    // 从i结点的左子结点开始,也就是2i+1处开始
    for (int k = i * 2 + 1; k < length; k = k * 2 + 1) {
      
      // 如果左子结点小于右子结点,k指向右子结点
      if (k + 1 < length && arr[k] < arr[k + 1]) {
        k++;
      }
      
      // 如果子节点大于父节点,将子节点值赋给父节点。不用进行交换。
      if (arr[k] > temp) {
        arr[i] = arr[k];
        i = k;
      } else {
        break;
      }
    }
    
    // 将temp值放到最终的位置
    arr[i] = temp;
  }
  
  // 交换元素
  public static void swap(int[] arr, int a, int b) {
    int temp = arr[a];
    arr[a] = arr[b];
    arr[b] = temp;
  }

  // 显示
  public static void display(String str, int[] arr) {
    System.out.println(str);
    for (int i = 0; i < arr.length; i++) {
      System.out.print(arr[i] + " ");
    }
    System.out.println();
  }
}

原始数据 :
27 83 96 38 11 9
构建中:
27 83 96 38 11 9
构建中:
27 83 96 38 11 9
构建中:
96 83 27 38 11 9
大顶堆 :
96 83 27 38 11 9
排序中:
83 38 27 9 11 96
排序中:
38 11 27 9 83 96
排序中:
27 11 9 38 83 96
排序中:
11 9 27 38 83 96
排序中:
9 11 27 38 83 96
排序结果:
9 11 27 38 83 96 阅读全文

关于Java排序算法-希尔排序(Shell Sort)

希尔排序又称“缩小增量排序”,是通过对直接插入排序进行改进得到的一种插入排序法。
基本思想:将整个待排序列分割成几个较小的子序列分别进行直接插入排序,待整个序列中的记录基本有序时,再对整个记录序列进行一次直接插入排序。
过程:设待排序列有n个记录, 首先取一个整数d1< n 作为步长, 将全部记录分为d1个子序列, 所有距离为d1的记录放在同一个子序列中, 在每个子序列中分别施行直接插入排序。然后缩小步长 , 如取 d2=d1/2,重复上述的子序列划分和排序工作。直到最后取dt=1, 将所有记录放在同一个序列中排序为止。

阅读全文

关于Java排序算法-快速排序(Quick Sort)

快速排序是对气泡排序的一种改进。
基本思想:通过一趟排序将待排序列分割成独立的两部分,其中一部分元素的排序码均比另一部分的排序码小,分别对这两部分继续进行排序,直至整个序列有序。
具体过程:设待排序列为 A[s..t],选取任意一个元素作为支点(基准元素,一般就选A[s]),然后从区间两端向中间依次比较元素,一旦发现前半部分有元素大于基准元素,后半部分有元素小于基准元素,则交换这两个元素,所有元素比较一遍后,最后把基准元素交换到两部分的中间,使得所有比基准元素大的都排在此基准元素的后面;所有比基准元素小的都放在此基准元素的前面。即该基准元素把序列 A[s..t] 分成两部分,此过程称为一次划分。

public class SortTest {
  public static void main(String[] args) {
    int[] arr = { 49, 38, 65, 97, 76, 13, 27, 49 };
    display("原始数据 : ", arr);

    // 快速排序
    quickSort(arr, 0, arr.length - 1);

    display("排序结果:", arr);
  }

  // 交换元素
  public static void swap(int[] arr, int a, int b) {
    int temp = arr[a];
    arr[a] = arr[b];
    arr[b] = temp;
  }

  // 显示
  public static void display(String str, int[] arr) {
    System.out.println(str);
    for (int i = 0; i < arr.length; i++) {
      System.out.print(arr[i] + " ");
    }
    System.out.println();
  }

  // 快速排序
  public static void quickSort(int[] arr, int s, int t) {
    // 递归算法,对区间a[s] ~a[t] 进行快速排序
    int i = s + 1, j = t;
    int temp = 0;
    int x = arr[s]; // 第一个为基准元素
    while (i <= j) {
      // 从左到右
      while (i <= j && arr[i] <= x) {
        i++;
      }
      
      // 从右到左
      while (i <= j && arr[j] >= x) {
        j--;
      }

      if (i < j) {
//				temp = arr[i];
//				arr[i] = arr[j];
//				arr[j] = temp;
        swap(arr, i, j);
        i++;
        j--;
      }
    }
    
    // 交换基准元素
    if (s != j) {
      arr[s] = arr[j];
      arr[j] = x;
    }
    
    // 处理左区间
    if (s < j - 1) {
      quickSort(arr, s, j - 1);
    }
    
    // 处理右区间
    if (j + 1 < t) {
      quickSort(arr, j + 1, t);
    }
  }

}

原始数据 :
49 38 65 97 76 13 27 49
排序结果:
13 27 38 49 49 65 76 97 阅读全文

关于Java排序算法-直接选择排序(Select Sort)

基本思想:每一趟排序,如第 i 趟 ( i = 0, 1, …, n-2) ,均在 待排序记录中选出排序码最小的记录, 作为有序序列中的第 i 个记录。包括直接选择排序和堆排序。
基本操作:第一趟从n个记录中选出排序码最小的记录与第1个记录交换;第二趟在余下的n-1个记录中再选出排序码最小的记录与第2个记录交换;依次类推,直至第n-1趟选出相应记录与第n-1个位置上的记录交换。

public class SortTest {
  public static void main(String[] args) {
    int[] arr = { 49, 38, 65, 97, 49, 13, 27, 76 };
    display("原始数据 : ", arr);
    // 选择排序
    selectSort(arr);
    display("排序结果:", arr);
  }

  // 交换元素
  public static void swap(int[] arr, int a, int b) {
    int temp = arr[a];
    arr[a] = arr[b];
    arr[b] = temp;
  }

  // 显示
  public static void display(String str, int[] arr) {
    System.out.println(str);
    for (int i = 0; i < arr.length; i++) {
      System.out.print(arr[i] + " ");
    }
    System.out.println();
  }

  // 选择排序
  public static void selectSort(int[] arr) {
    int k, j;
    for (int i = 0; i < arr.length; i++) {
      k = i;
      for (j = i + 1; j < arr.length; j++) {
        if (arr[j] < arr[k])
          k = j;
      }
      if (k != i) {
        swap(arr, i, k);
      }
    }
  }

}

原始数据 :
49 38 65 97 49 13 27 76
排序结果:
13 27 38 49 49 65 76 97 阅读全文

关于Java排序算法-直接插入排序(Insert Sort)

基本思想:当插入第i (i ≥ 1) 个记录时, 前面的A[0], A[1], …, A[i-1]已经排好序。这时, 用A[i]的排序码与A[i-1], A[i-2], …的排序码顺序进行比较, 找到插入位置即将A[i]插入, 原来位置上的记录向后顺移。
过程:首先将待排序序列的第 1 个数据元素看成是一个有序的子序列,然后依次将第 2 个数据元素、第 3 个数据元素、…… 插入到这个有序序列。

阅读全文