首页 > 代码库 > Java数据结构与算法(2) - 排序(冒泡、插入和选择排序)
Java数据结构与算法(2) - 排序(冒泡、插入和选择排序)
排序需要掌握的有冒泡排序,插入排序和选择排序。
冒泡排序: 外层循环从后往前,内存循环从前往后到外层循环,相邻数组项两两比较,将较大的值后移。
插入排序: 从排序过程的中间开始(程序从第二个数组项开始a[1]),此时队列已经拍好了一部分。此时,将后边的数组项一次插入到已经排好序的部分队列中。
选择排序: 从第一个数组项开始,找到包括该数组项在内的所有往后数组项中的最小项与当前项进行交换,其实相当于依次将最小值往前冒泡。
示例代码:
package chap03.BubbleSort;// bubbleSort.java// demonstrates bubble sort// to run this program: C>java BubbleSortAppclass ArrayBub { private long[] a; private int nElems; public ArrayBub(int max) { a = new long[max]; nElems = 0; } public void insert(long value) { a[nElems] = value; nElems++; } public void display() { for (int j = 0; j < nElems; j++) { System.out.print(a[j] + " "); } System.out.println(""); } // 冒泡排序 public void bubbleSort() { int out, in; for (out = nElems - 1; out > 1; out--) { for (in = 0; in < out; in++) { if (a[in] > a[in + 1]) { swap(in, in + 1); } } } } // 插入排序 public void insertionSort() { int in, out; // out is dividing line for (out = 1; out < nElems; out++) { // remove marked item long temp = a[out]; // start shifts at out in = out; while (in > 0 && a[in - 1] >= temp) { a[in] = a[in - 1]; --in; } a[in] = temp; } } // 选择排序 public void selectionSort() { int out, in, min; for (out = 0; out < nElems - 1; out++) { min = out; for (in = out + 1; in < nElems; in++) { if (a[in] < a[min]) { min = in; } } swap(out, min); } } private void swap(int one, int two) { long temp = a[one]; a[one] = a[two]; a[two] = temp; }}class BubbleSortApp { public static void main(String[] args) { int maxSize = 100; ArrayBub arr; arr = new ArrayBub(maxSize); arr.insert(77); arr.insert(99); arr.insert(44); arr.insert(55); arr.insert(22); arr.insert(88); arr.insert(11); arr.insert(00); arr.insert(66); arr.insert(33); arr.display(); arr.bubbleSort(); arr.display(); }}
Java数据结构与算法(2) - 排序(冒泡、插入和选择排序)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。