线性结构（数组、队列、链表、栈）：数据元素之前存一一对应关系。
顺序存储结构/顺序表（数组）：存储元素地址连续。
链式存储结构（链表）：存储元素地址不一定连续。可以充分利用内存空间。
非线性结构（二维数组、多维数、广义表、树结构、图结构）。
应用场景：棋盘、地图等。
package sparseArray; public class SparseArray { /*待完成: 将稀疏数组用IO流保存到文件，再重文件中获取稀疏数组*/ public static void main(String[] args) { // 创建一个原始的二维数组11*11 // 0:表示没有棋子，1:表示 黑子， 2:表示 蓝子 int[][] chessMap = new int[11][11]; chessMap[1][2] = 1; chessMap[2][3] = 2; chessMap[4][5] = 1; chessMap[7][9] = 2; // 打印原数组 for (int[] chessArray : chessMap) { for (int chess : chessArray) { System.out.printf("%d\t", chess); } System.out.println(); } // 棋盘中棋子的个数 int sum = 0; for (int i = 0; i < chessMap.length; i++) { for (int j = 0; j < chessMap[i].length; j++) { if (chessMap[i][j] != 0) { sum++; } } } // 创建稀疏数组 int count = 0; int[][] sparseArray = new int[sum + 1][3]; sparseArray[0][0] = chessMap.length; sparseArray[0][1] = chessMap[0].length; sparseArray[0][2] = sum; for (int i = 0; i < chessMap.length; i++) { for (int j = 0; j < chessMap[i].length; j++) { if (chessMap[i][j] != 0) { count++; sparseArray[count][0] = i; sparseArray[count][1] = j; sparseArray[count][2] = chessMap[i][j]; } } } // 打印稀疏数组 for (int[] sparseArr : sparseArray) { for (int element : sparseArr) { System.out.printf("%d\t", element); } System.out.println(); } // 将稀疏数组还原 int[][] chessMap2 = new int[sparseArray[0][0]][sparseArray[0][1]]; for (int i = 1; i < sparseArray.length; i++) { chessMap2[sparseArray[i][0]][sparseArray[i][1]] = sparseArray[i][2]; } // 打印还原数组 for (int[] chessArray2 : chessMap2) { for (int chess2 : chessArray2) { System.out.printf("%d\t", chess2); } System.out.println(); } } }应用场景：银行排队。
环形队列
package arrayQueue; import java.util.Scanner; public class CircleArrayQueueDemo { public static void main(String[] args) { // 创建一个队列 CircleArrayQueue circleArrayQueue = new CircleArrayQueue(4);//说明设置4,其队列的有效数据最大为3 Scanner input = new Scanner(System.in); System.out.println("s(show):显示队列\na(add):添加数据到队列\ng(从队列取出数据)\nh(head):查看队列头的数据\ne(exit):退出程序"); char key = ' '; while (key != 'e') { key = input.next().charAt(0); switch (key) { case 's': try { circleArrayQueue.showQueue(); } catch (Exception e) { System.out.println(e.getMessage()); } break; case 'a': System.out.print("请输入添加的数据: "); try { circleArrayQueue.addQueue(input.nextInt()); } catch (Exception e) { System.out.println(e.getMessage()); } break; case 'g': try { System.out.println("取出的数据为" + circleArrayQueue.getQueue()); } catch (Exception e) { System.out.println(e.getMessage()); } break; case 'h': try { System.out.println("队列头数据为" + circleArrayQueue.headQueue()); } catch (Exception e) { System.out.println(e.getMessage()); } break; case 'e': System.out.println("您已选择离开"); break; default: System.out.println("选择的选项不存在"); } } } } class CircleArrayQueue { private int maxSize;//表示数组的最大容量 private int front;//front指向队列的第一个元素，也就是说array[front]就是队列的第一个元素 // front初始值为0 private int rear;//rear指向队列的最后一个元素的后一个位置，因为希望空出一个空间作为约定 // rear初始值为0 private int[] array;//该数据用于存放数据，模拟队列 public CircleArrayQueue(int arrMaxSize) { maxSize = arrMaxSize; array = new int[maxSize]; } // 判断队列是否满 public boolean isFull() { return (rear + 1) % maxSize == front; } // 判断数据是否为空 public boolean isEmpty() { return rear == front; } // 添加数据到队列 public void addQueue(int n) { if (!isFull()) { array[rear] = n; rear = ++rear % maxSize; } else { System.out.println("队列已满,不能加入数据！"); } } // 获取队列的数据 public int getQueue() { if (!isEmpty()) { int value = array[front]; front = ++front % maxSize; return value; } else { throw new RuntimeException("队列为空，不能获取数据!"); } } // 显示队列的所有数据 public void showQueue() { // 遍历 if (!isEmpty()) { for (int i = front; i < front + size(); i++) { System.out.printf("array[%d]=%d\n", i % maxSize, array[i % maxSize]); } } else { throw new RuntimeException("队列为空!"); } } // 求出当前队列有效数据的个数 public int size() { return (rear + maxSize - front) % maxSize; } // 显示当前队列的首元素 public int headQueue() { if (!isEmpty()) { return array[front]; } else { throw new RuntimeException("队列为空!"); } } }
腾讯面试题：单链表反转
package linkedList; import java.util.Stack; public class SingleLinkedListDemo { public static void main(String[] args) { // 进行测试 // 先创建节点 HeroNode hero = new HeroNode(1, "宋江", "及时雨"); HeroNode hero1 = new HeroNode(2, "卢俊义", "玉麒麟"); HeroNode hero2 = new HeroNode(3, "吴用", "智多星"); HeroNode hero3 = new HeroNode(4, "林冲", "豹子头"); // 创建一个链表 SingleLinkedList singleLinkedList = new SingleLinkedList(); /*singleLinkedList.add(hero); singleLinkedList.add(hero1); singleLinkedList.add(hero2); singleLinkedList.add(hero3);*/ // 按照顺序插入 singleLinkedList.addByOrder(hero3); singleLinkedList.addByOrder(hero1); singleLinkedList.addByOrder(hero); singleLinkedList.addByOrder(hero2); singleLinkedList.list(); // 修改信息 /*HeroNode newHeroNode = new HeroNode(4, "老霖", "小包子"); HeroNode newHeroNode2 = new HeroNode(5, "三郎", "拼命三郎"); singleLinkedList.update(newHeroNode); singleLinkedList.update(newHeroNode2);*/ // 删除节点 /* singleLinkedList.delete(1); singleLinkedList.delete(4); singleLinkedList.delete(5); singleLinkedList.list();*/ // 获取链表有效节点个数 /*System.out.println("有效的节点个数为 "+SingleLinkedList.getLength(singleLinkedList.getHead()));*/ // 获取链表倒数第K个节点 /*System.out.println("倒数第二个节点为 "+SingleLinkedList.findLastIndexNode(singleLinkedList.getHead(),2));*/ // 单链表反转 /*SingleLinkedList.reverseList(singleLinkedList.getHead()); singleLinkedList.list();*/ // 逆序打印链表 SingleLinkedList.reversePrint(singleLinkedList.getHead()); } } //定义HeroNode，每个HeroNode对象就是一个节点 class HeroNode { public int no; public String name; public String nickname; public HeroNode next;//指向下一个节点 // 构造方法 public HeroNode(int no, String name, String nickname) { this.no = no; this.name = name; this.nickname = nickname; } // 为了显示方法，我们重写toString @Override public String toString() { return "HeroNode{" + "no=" + no + ", name='" + name + '\'' + ", nickname='" + nickname + '}'; } } //定义SingleLinkedList 管理我们的英雄 class SingleLinkedList { // 先初始化一个头节点不要动，不存放具体的数据 private HeroNode head = new HeroNode(0, "", ""); public HeroNode getHead() { return head; } // 添加节点到单项链表 // 思路，当不考虑编号顺序时 // 1.找到当前链表的最后节点 // 2.将最后这个节点的next 指向 新的节点 public void add(HeroNode heroNode) { // 因为head节点不能动，因此我们需要一个辅助的变量temp HeroNode temp = head; // 遍历链表，找到最后 while (true) { if (temp.next == null) { break; } temp = temp.next; } // 当退出while循环时，temp就指向链表最后 // 将最后这个节点指向新的节点 temp.next = heroNode; } //第二种方式在添加英雄时，根据排名奖英雄插入到指定位置 //（如果单链表中已有这个排名，则添加失败，并给出提示） public void addByOrder(HeroNode heroNode) { // 因为头节点不能动，因此我们仍然通过一个辅助指针（变量）来帮助找到添加的位置 // 因此我们找的temp是位于添加位置的前一个节点，否则插入不了 HeroNode temp = head; boolean flag = false;//flag标志添加的编号是否存在，默认为false while (true) { if (temp.next == null) {//说明temp已经在链表的最后 break; } if (temp.next.no > heroNode.no) {//位置找到就在temp的后面插入 break; } else if (temp.next.no == heroNode.no) {//说明希望添加的heroNode的编号已经存在 flag = true; break; } temp = temp.next;//后移，遍历当前链表 } if (flag) {//不能添加，编号已经存在 System.out.printf("准备插入的英雄编号 %d 已经存在,不能添加！\n", heroNode.no); } else { //插入到链表temp的后面 heroNode.next = temp.next; temp.next = heroNode; } } //删除节点 //1.head不能动，因此我们需要一个temp辅助节点找到待删除节点的前一个节点 //2.说明我们在比较是，是temp.next.no和要删除的节点的比较 public void delete(int no) { if (head.next != null) { HeroNode temp = head; boolean flag = false;//用于标志要删除的节点是否找到 while (true) { if (temp.next == null) {//链表指针已经到达链表最后 break; } if (temp.next.no == no) {//找到待删除节点的前一个节点temp flag = true; break; } temp = temp.next;//temp后移，遍历 } if (flag) {//进行删除 temp.next = temp.next.next; } else { System.out.printf("要删除的 %d 不存在，删除失败!\n", no); } } else { System.out.println("链表为空!"); } } //修改节点的信息，根据no编号来修改，即no编号不能改。 //根据newHeroNode的no来修改即可 public void update(HeroNode newHeroNode) { if (head.next != null) { boolean flag = false; //节点是否找到的标志 HeroNode temp = head.next; //定义一个辅助变量 while (true) { if (temp == null) {//指针已经到达链表最后，没有找到节点 break; } else if (temp.no == newHeroNode.no) {//找到要修改的节点 flag = true; break; } temp = temp.next; } if (flag) {//更新信息 temp.name = newHeroNode.name; temp.nickname = newHeroNode.nickname; } else { System.out.printf("没有找到编号为 %d 的节点，修改失败!\n", newHeroNode.no); } } else { System.out.println("链表为空!"); } } // 显示链表[遍历] public void list() { // 判断链表是否为空 if (head.next == null) { System.out.println("链表为空!"); return; } // 因为头节点不能动，因此我们需要一个辅助变量来遍历 HeroNode temp = head.next; while (true) { // 判断链表是否为空 if (temp == null) { break; } // 输出节点的信息 System.out.println(temp); // 将temp后移，此处不后移出现死循环 temp = temp.next; } } // 面试题 //获取单链表有效节点的个数（如果是带头节点的链表，不统计头节点） /** * @param head 链表的头节点 * @return 返回有效节点的个数 */ public static int getLength(HeroNode head) { int length = 0; if (head.next != null) { HeroNode current = head;//定义一个辅助（指针）变量，这里我们没有统计头节点 while (current.next != null) { length++; current = current.next; } } return length; } // 新浪 //查找单链表中的倒数第K个节点 // 1.编写一个方法，接受head节点，同时接收一个index // 2.index 表示是倒数第index个节点 // 3.先把链表重头到尾遍历，得到链表的总的长度getLength // 4.得到size后，我们从链表的第一个开始遍历(size-index)个，就可以得到 // 5.如果找到了则返回节点，否则返回null public static HeroNode findLastIndexNode(HeroNode head, int index) { // 判断如果链表为空，返回null if (head.next == null) { return null; } // 第一个遍历得到链表的长度（节点个数） int size = getLength(head); // 第二次遍历 size-index 位置，就是我们倒数的第K个节点 // 先做一个index校验 if (index <= 0 || index > size) { return null; } // 定义辅助指针（变量） HeroNode current = head.next; for (int i = 0; i < size - index; i++) { current = current.next; } return current; } // 腾讯 //单链表的反转 public static void reverseList(HeroNode head) { // 如果当前链表为空，或者自由一个节点，无需反转，直接返回 if (head.next == null || head.next.next == null) { return; } // 定义一个辅助指针（变量），帮助我们遍历原来的链表 HeroNode current = head.next; HeroNode next = null;//指向当前节点[current]的下一个节点 HeroNode reverseHead = new HeroNode(0, "", ""); // 遍历原来的链表，每遍历一个节点，就将其取出并放在新的链表reverseHead的最前端 while (current != null) { next = current.next;//暂时保存当前节点的下一个节点，因为后面需要使用 current.next = reverseHead.next;//将当前的下一个节点指向新链表的最前端 reverseHead.next = current;//将新链表reserveHead指向的下一个节点指向刚挂载到新链表的节点上 current = next;//让current后移 } head.next = reverseHead.next;//将head.next指向reverseHead.next，实现单链表反转 } // 百度 //反向打印单链表内容 // 利用栈这个数据结构，将各个节点压入栈中，利用栈先进后出的特点逆序打印 public static void reversePrint(HeroNode head) { if (head.next == null) {//空链表，不能打印 return; } HeroNode current = head.next; // 创建一个栈，将链表数据压入 Stack<HeroNode> stack = new Stack<>(); while (current != null) { stack.push(current); current = current.next; } // 逆序打印 while (!stack.empty()) { System.out.println(stack.pop()); } } }package linkedList; public class DoubleLinkedListDemo { public static void main(String[] args) { // 进行测试 // 先创建节点 HeroNodeOD heroOD = new HeroNodeOD(1, "宋江", "及时雨"); HeroNodeOD heroOD1 = new HeroNodeOD(2, "卢俊义", "玉麒麟"); HeroNodeOD heroOD2 = new HeroNodeOD(3, "吴用", "智多星"); HeroNodeOD heroOD3 = new HeroNodeOD(4, "林冲", "豹子头"); // 创建一个链表 DoubleLinkedList doubleLinkedList = new DoubleLinkedList(); // 添加 /*doubleLinkedList.add(heroOD); doubleLinkedList.add(heroOD1); doubleLinkedList.add(heroOD2); doubleLinkedList.add(heroOD3);*/ // 按顺序添加 doubleLinkedList.addByOrder(heroOD3); doubleLinkedList.addByOrder(heroOD1); doubleLinkedList.addByOrder(heroOD); doubleLinkedList.addByOrder(heroOD2); // 遍历显示 doubleLinkedList.list(); // 修改 HeroNodeOD newHeroNode = new HeroNodeOD(4, "刘聪", "一尾鱼"); doubleLinkedList.update(newHeroNode); doubleLinkedList.list(); // 删除 doubleLinkedList.delete(2); doubleLinkedList.list(); } } //定义HeroNodeOD，每个HeroNodeOD对象就是一个节点 class HeroNodeOD { public int no; public String name; public String nickname; public HeroNodeOD next;//指向下一个节点 public HeroNodeOD prev;//指向前一个节点 // 构造方法 public HeroNodeOD(int no, String name, String nickname) { this.no = no; this.name = name; this.nickname = nickname; } // 为了显示方法，我们重写toString @Override public String toString() { return "HeroNode{" + "no=" + no + ", name='" + name + '\'' + ", nickname='" + nickname + '}'; } } //定义DoubleLinkedList 管理我们的英雄 class DoubleLinkedList { // 先初始化一个头节点不要动，不存放具体的数据 private HeroNodeOD head = new HeroNodeOD(0, "", ""); public HeroNodeOD getHead() { return head; } //添加一个节点到双向链表的最后 public void add(HeroNodeOD newHeroNodeOD) { // 因为head节点不能动，因此我们需要一个辅助的变量temp HeroNodeOD temp = head; // 遍历链表，找到最后 while (true) { if (temp.next == null) { break; } temp = temp.next; } // 当退出while循环时，temp就指向链表最后 temp.next = newHeroNodeOD; newHeroNodeOD.prev = temp; } //第二种方式在添加英雄时，根据排名奖英雄插入到指定位置 //（如果双向链表中已有这个排名，则添加失败，并给出提示） public void addByOrder(HeroNodeOD newheroNodeOD) { // 因为头结点不能动，因此我们仍然通过一个辅助指针（变量）来帮助找到添加的位置 // 因此我们找的temp是位于添加位置的前一个节点，否则插入不了 HeroNodeOD temp = head; boolean flag = false;//flag标志添加的编号是否存在，默认为false while (true) { if (temp.next == null) {//说明temp已经在链表的最后 break; } if (temp.next.no > newheroNodeOD.no) {//位置找到就在temp的后面插入 break; } else if (temp.next.no == newheroNodeOD.no) {//说明希望添加的heroNode的编号已经存在 flag = true; break; } temp = temp.next;//后移，遍历当前链表 } if (flag) {//不能添加，编号已经存在 System.out.printf("准备插入的英雄编号 %d 已经存在,不能添加！\n", newheroNodeOD.no); } else { //插入到链表temp的后面 newheroNodeOD.next = temp.next; if (temp.next != null) { temp.next.prev = newheroNodeOD; } temp.next = newheroNodeOD; newheroNodeOD.prev = temp; } } //从双向链表中删除一个节点 // 1.对于双向链表我们可以直接找到要删除的这个节点 // 2.找到偶，自我即可删除 public void delete(int no) { if (head.next != null) { HeroNodeOD temp = head; boolean flag = false;//用于标志要删除的节点是否找到 while (true) { if (temp.next == null) {//链表指针已经到达链表最后 break; } if (temp.no == no) {//找到待删除节点 flag = true; break; } temp = temp.next;//temp后移，遍历 } if (flag) {//进行删除 temp.prev.next = temp.next; if (temp.next != null) {//避免要删除的节点是双向链表的最后一个而出现空指针现象 temp.next.prev = temp.prev; } } else { System.out.printf("要删除的 %d 不存在，删除失败!\n", no); } } else { System.out.println("链表为空!"); } } //修改双线链表中节点的内容（和单项链表一样） public void update(HeroNodeOD newHeroNodeOD) { if (head.next != null) { boolean flag = false; //节点是否找到的标志 HeroNodeOD temp = head.next; //定义一个辅助变量 while (true) { if (temp == null) {//指针已经到达链表最后，没有找到节点 break; } else if (temp.no == newHeroNodeOD.no) {//找到要修改的节点 flag = true; break; } temp = temp.next; } if (flag) {//更新信息 temp.name = newHeroNodeOD.name; temp.nickname = newHeroNodeOD.nickname; } else { System.out.printf("没有找到编号为 %d 的节点，修改失败!\n", newHeroNodeOD.no); } } else { System.out.println("链表为空!"); } } //遍历显示双线链表内容 public void list() { // 判断链表是否为空 if (head.next == null) { System.out.println("链表为空!"); return; } // 因为头节点不能动，因此我们需要一个辅助变量来遍历 HeroNodeOD temp = head.next; while (true) { // 判断链表是否为空 if (temp == null) { break; } // 输出节点的信息 System.out.println(temp); // 将temp后移，此处不后移出现死循环 temp = temp.next; } } }
package linkedList; public class Josephu { public static void main(String[] args) { // 创建单向环形链表 CircleSingleLinkedList circleSingleLinkedList = new CircleSingleLinkedList(); circleSingleLinkedList.addPerson(125); circleSingleLinkedList.list(); // 按照规则“出圈” circleSingleLinkedList.countPerson(10, 20, 125); } } class Person { private int no;//编号 private Person next;//指向下一个节点，默认null public Person(int no) { this.no = no; } public int getNo() { return no; } public Person getNext() { return next; } public void setNext(Person next) { this.next = next; } } //创建一个单向环形链表 class CircleSingleLinkedList { // 创建一个first节点，当前没有编号 private Person first = null; //添加小孩节点，构成一个环形链表 public void addPerson(int nums) { // nums做一个数据校验 if (nums < 1) { System.out.println("添加个数不能小于1！"); return; } Person currentPerson = null;//辅助指针，帮助构建环形链表 // 使用for循环创建环形链表 for (int i = 1; i <= nums; i++) { // 根据编号，创建节点 Person person = new Person(i); // 如果是第一个节点 if (i == 1) { first = person; first.setNext(first);//构成环 currentPerson = first;//让currentPerson指向第一个小孩 } else { currentPerson.setNext(person); person.setNext(first); currentPerson = person; } } } //遍历当前环形链表 public void list() { // 链表是否为空 if (first == null) { System.out.println("环形链表无节点！"); return; } // 因为first不能动，因此我们仍然使用一个辅助指针完成遍历 Person currentPerson = first; while (true) { System.out.println("编号: " + currentPerson.getNo()); if (currentPerson.getNext() == first) {//说明已经遍历完毕 break; } currentPerson = currentPerson.getNext();//currentPerson后移 } } //根据用户的输入，计算出人出圈的顺序 /** * @param startNo 表示出从第几个人开始数数 * @param countNum 表示数几下 * @param nums 表示最初由多少个小孩在圈中 */ public void countPerson(int startNo, int countNum, int nums) { // 先对数据进行校验 if (first == null || startNo < 1 || startNo > nums) { System.out.println("参数输入有误,请重新输入"); return; } // 创建要给辅助指针，帮助完成小孩出圈 Person helper = first; // 需要创建一个辅助指针（变量）helper，实现应该指向环形链表的最后这个节点 while (true) { if (helper.getNext() == first) {//说明helper指向最后节点 break; } helper = helper.getNext(); } // 报数前，先让 first 和 helper 移动 k-1 次 for (int i = 0; i < startNo - 1; i++) { first = first.getNext(); helper = helper.getNext(); } // 当小孩报数时，让 first 和 helper 指针同时移动 m-1 次，然后出圈 // 循环操作直到圈中只有一个节点 while (true) { if (helper == first) {//说明圈中只有一个节点 break; } // 让 first 和 helper 指针同时移动 countNum-1 次 for (int i = 0; i < countNum - 1; i++) { first = first.getNext(); helper = helper.getNext(); } // 这时 first 指向的节点，就是要出圈的节点 System.out.printf("编号: %d 出圈\n", first.getNo()); first = first.getNext(); helper.setNext(first); } System.out.println("圈中剩余节点的编号: " + first.getNo()); } }
package stacks; import java.util.Scanner; public class ArrayStackDemo { public static void main(String[] args) { // 创建一个ArrayStack对象 ->表示栈 ArrayStack stack = new ArrayStack(4); boolean loop = true; String key = ""; Scanner input = new Scanner(System.in); System.out.println("push:添加数据到栈（入栈）"); System.out.println("pop:表示从栈取出数据（出栈）"); System.out.println("show:显示栈"); System.out.println("exit:退出程序"); while (loop) { key = input.next(); switch (key) { case "push": System.out.print("请输入数据: "); stack.push(input.nextInt()); break; case "pop": System.out.println("出栈的数据是: " + stack.pop()); break; case "show": stack.list(); break; case "exit": loop = false; break; default: System.out.println("输入的选项不存在！"); } } } } //定义一个ArrayStack表示栈 class ArrayStack { private int maxSize;//栈的大小 private int[] stack;//数组，数组模拟栈，数据就放在该数组 private int top = -1;//top表示栈定，初始化为-1 public ArrayStack(int maxSize) { this.maxSize = maxSize; stack = new int[this.maxSize]; } //栈满 public boolean isFull() { return top == maxSize - 1; } //栈空 public boolean isEmpty() { return top == -1; } //入栈 push public void push(int value) { // 先判断栈是否满 if (isFull()) { System.out.println("栈满,添加失败"); } else { stack[++top] = value; } } //出栈 pop 将栈顶数据返回 public int pop() { // 先判断栈是否为空 if (isEmpty()) { throw new RuntimeException("栈空，无数据可返回"); } else { int value = stack[top--]; return value; } } //显示栈的情况[遍历栈]，遍历是，需要从栈顶开始显示数据 public void list() { if (isEmpty()) { System.out.println("栈空，无数据可以遍历"); } // 需要从栈顶显示数据 for (int i = top; i >= 0; i--) { System.out.printf("stack[%d]=%d\n", i, stack[i]); } } }
希尔排序【交换式/位移式】算法实现
package insertionSorting; import java.text.SimpleDateFormat; import java.util.Arrays; import java.util.Date; public class ShellSort { public static void main(String[] args) { // 创建含有80000个整型的随机数组 int[] arr = new int[80000]; for (int i = 0; i < arr.length; i++) { arr[i] = (int) (Math.random() * 800000); } SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss"); Date date = new Date(); String dateStr = simpleDateFormat.format(date); System.out.println("排序前的时间: " + dateStr); // shellSort(arr); shellSort1(arr); Date date1 = new Date(); dateStr = simpleDateFormat.format(date1); System.out.println("排序后的时间: " + dateStr); // int[] arr = {8,9,1,7,2,3,5,4,6,0}; } /* // 使用逐步推导的方式来编写希尔排序 // 希尔排序时，对有序序列在插入时采用交换法 // 思路（算法）===> 代码 private static void shellSort(int[] arr) { int temp = 0; int count = 0; // 根据前面的逐步分析，使用循环处理 for (int gap = arr.length / 2; gap > 0; gap /=2){ for (int i = gap; i < arr.length; i++){ // 遍历各组中的所有元素（共gap组，每组有arr.length/gap个元素），步长gap for (int j = i - gap; j >= 0; j -= gap){ // 如果当前元素大于加上步长后的那个元素,说明交换 if (arr[j] > arr[j + gap]){ temp = arr[j]; arr[j] = arr[j + gap]; arr[j + gap] = temp; } } } // System.out.println("希尔排序第"+ (++count) + "轮=" + Arrays.toString(arr)); } } */ //对交换式的希尔排序进行优化 -> 位移法 private static void shellSort1(int[] arr) { for (int gap = arr.length / 2; gap > 0; gap /= 2) { // 从第gap个元素，逐个对其所在的组进行直接插入排序 for (int i = gap; i < arr.length; i++) { int j = i; int temp = arr[j]; if (arr[j] < arr[j - gap]) { while (j - gap >= 0 && temp < arr[j - gap]) { // 移动 arr[j] = arr[j - gap]; j -= gap; } // 当退出while后，就给temp找到插入的位置 arr[j] = temp; } } } } }
