yuan
- 浏览: 269348 次
- 性别:
- 来自: 尤溪
-
文章分类
最新评论
-
palytoxin：
我现在也发现是这样
关于分享 -
float2net：
Java社区，分享有利于提高。
关于分享 -
hz_qiuyuanxin：
头晕啊，啊邱
RSpec学习笔记 -
reyesyang：
...
关于分享 -
Hooopo：
一般实现map都先实现each
在 Ruby 中对树状结构(tree)进行 map 操作
每篇笔记都会附上随书的Applet演示程序，有算法看不明白的，可以下载Applet运行起来（直接打开html文件即可），可以很容易地看清楚算法的每一步。
冒泡排序的原理很简单，拿整数数组的升序排序来说：从头到尾循环地比较相邻的两个数字，如果前一个数字比后一个大，则交换它们的位置，然后拿较大的这个数字跟下一个比较；如果前一个数字比后一个小，它们的位置不动，直接拿较大的数字跟下一个比较，这样循环一次完毕，最大的数字被排到了最后。接着开始第二轮循环，再从头到尾循环比较相信的两个数字，循环完毕后，第二大的数字被排到了倒数第二的位置上。长度为N的数组一共需要N次循环（其实最后一次没有必要），最坏的情况下（逆序），第1次循环要交换数字N-1次，第2次循环要交换数字N-2次，最后一次循环要交换0次，总共交换(N-1)*N/2 = (N^2-N)/2次，约N^2/2次（忽略N次不会有很大差别，特别是在N很大的时候）。如果数据是随机的，平均每次排序需要交换数字N^2/4次，也就是说交换次数和N^2/4成正比，由于常数不算在大O表示法中，可以忽略掉这个4，认为冒泡排序运行需要O(N^2)时间级别。
以下是冒泡排序代码：
选择排序法是冒泡排序法的改进，冒泡排序在最坏的情况下每次循环比较的时候都进行交换操作，而选择排序每循环一次只要交换数字1次。原理是：在第一次循环的时候用一个临时变量指向数组第1个位置，假设第1个位置是最小值，依次比较数组右边的其它数字，当遇到比第1个位置的数更小的值时，将临时变量指向这个更小的数的位置，循环过一次，便得到整个数组中最小的值，把它与第1个位置的数字交换，第一次循环完毕。第二次循环从第2个位置开始……一共需要N次循环（同样，最后一次也没有必要）。这样，选择排序法交换数字的次数跟数组长度成正比，用大O表示法表示为O(N)。
下面的代码中加入了选择排序法selectionSort：
插入排序法保持数组的前面一部分有序，并不断地把后面无序的数据插入到前面有序的一部分，同时仍然保持前面的数据有序。这里仍然用整数数组的升序排序来说明其原理：首先假设数组第1个数据为有序数组（虽然只有1个数据，但那肯定是有序的数组），然后将第2个数据与前面1个数据对比，如果第2个数据比前一个小，就先把第2个数据保存到临时变量中，然后依次往前循环，与前面的每个数据（第一次循环只有1个）作比较，如果前面的数据比临时变量大，就把前面的数据往后移1个位置（复制到后一个位置上），直到遇到比临时变量小的数据，把临时变量插入到比它小的那个数据的后面。如果对比到了下标为0的数据之后仍然没有比临时变量小的数据，就直接把临时变量插入到下标为0的位置上。用插入排序法进行逆序排序的情况下，第1次循环需要3次复制（复制出临时变量，把有序部分后移的时候也要复制，再把临时变量复制到正确的位置），第2次循环需要4次复制……第N-1次循环（因为是从第2个数据开始，所以只有N-1次）需要N+1次复制，一共(N^2+3N+3)/2次复制。如果数组中的数据是随机的，则平均需要(N^2+3N+3)/4次复制。同样，用大O表示法的时候，把常数3与3/4去掉（可以看作(N^2+3N)/4 + 3/4），再忽略掉3N，可以认为插入排序需要O(N^2)级别时间。但是一次复制与一次交换消耗的时间不同（一次交换有3次复制），所以插入排序法比冒泡排序法快得多，比选择排序略快。
以下代码中添加了插入排序法insertionSort：
奇偶排序法的思路是在数组中重复两趟扫描。第一趟扫描选择所有的数据项对，a[j]和a[j+1]，j是奇数(j=1, 3, 5……)。如果它们的关键字的值次序颠倒，就交换它们。第二趟扫描对所有的偶数数据项进行同样的操作(j=2, 4, 6……)。重复进行这样两趟的排序直到数组全部有序。
下面的代码是我原来的写法：
后来有朋友提出建议，我小小的改动了一下，对随机数组排序的效率略有提高：
和冒泡排序法一样，奇偶排序的时间复杂度为O(N^2)。
以上四种算法的运行效率我在本机上测试了一下，结果如下：
冒泡排序法对长度为1万的数组进行逆序排序，平均花费时间0.235秒；对随机数组进行升序排序，平均花费时间0.329秒。。。。这个这个。。。
选择排序法对长度为1万的数组进行逆序排序，平均花费时间0.188秒；对随机数组进行升序排序，平均花费时间0.218秒…………
插入排序法对长度为1万的数组进行逆序排序，平均花费时间0.141秒；对随机数组进行升序排序，平均花费时间0.078秒。（这回才正常，相当奇怪呀……我写的算法应该没有错吧，为什么冒泡排序和选择排序在逆序排序的时候比较快呢？？
具体原因暂时先参考问答频道这里http://www.iteye.com/problems/9236）
奇偶排序法对长度为1万的数组进行逆序排序，平均花费时间0.203秒；对随机数组进行升序排序，平均花费时间0.266秒。。。
昨天复习了链表一章，增加了一个表插入排序法，同时用泛型改写了一下以前的各排序算法。测试结果是：
附上时间测试代码：
冒泡排序法
冒泡排序的原理很简单，拿整数数组的升序排序来说：从头到尾循环地比较相邻的两个数字，如果前一个数字比后一个大，则交换它们的位置，然后拿较大的这个数字跟下一个比较；如果前一个数字比后一个小，它们的位置不动，直接拿较大的数字跟下一个比较，这样循环一次完毕，最大的数字被排到了最后。接着开始第二轮循环，再从头到尾循环比较相信的两个数字，循环完毕后，第二大的数字被排到了倒数第二的位置上。长度为N的数组一共需要N次循环（其实最后一次没有必要），最坏的情况下（逆序），第1次循环要交换数字N-1次，第2次循环要交换数字N-2次，最后一次循环要交换0次，总共交换(N-1)*N/2 = (N^2-N)/2次，约N^2/2次（忽略N次不会有很大差别，特别是在N很大的时候）。如果数据是随机的，平均每次排序需要交换数字N^2/4次，也就是说交换次数和N^2/4成正比，由于常数不算在大O表示法中，可以忽略掉这个4，认为冒泡排序运行需要O(N^2)时间级别。
以下是冒泡排序代码：
package dsaa.array;
/**
* @(#)ArrayUtil.java 2008-12-25 下午08:44:46
*
* @author Qiu Maoyuan
* Array Util
*/
public class ArrayUtil {
public static void bubbleSort(int[] array){
for(int i=0; i<array.length - 1; i++){
for(int j=0; j<array.length - i - 1; j++){
if(array[j]>array[j + 1]){
swap(array, j, j + 1);
}
}
}
}
private static void swap(int[] array, int index1, int index2) {
int temp = array[index1];
array[index1] = array[index2];
array[index2] = temp;
}
}
选择排序法
选择排序法是冒泡排序法的改进，冒泡排序在最坏的情况下每次循环比较的时候都进行交换操作，而选择排序每循环一次只要交换数字1次。原理是：在第一次循环的时候用一个临时变量指向数组第1个位置，假设第1个位置是最小值，依次比较数组右边的其它数字，当遇到比第1个位置的数更小的值时，将临时变量指向这个更小的数的位置，循环过一次，便得到整个数组中最小的值，把它与第1个位置的数字交换，第一次循环完毕。第二次循环从第2个位置开始……一共需要N次循环（同样，最后一次也没有必要）。这样，选择排序法交换数字的次数跟数组长度成正比，用大O表示法表示为O(N)。
下面的代码中加入了选择排序法selectionSort：
package dsaa.array;
/**
* @(#)ArrayUtil.java 2008-12-25 下午08:44:46
*
* @author Qiu Maoyuan
* Array Util
*/
public class ArrayUtil {
public static void bubbleSort(int[] array){
for(int i=0; i<array.length - 1; i++){
for(int j=0; j<array.length - i - 1; j++){
if(array[j]>array[j + 1]){
swap(array, j, j + 1);
}
}
}
}
public static void selectionSort(int[] array){
for(int i=0; i<array.length - 1; i++){
int minIndex = i;
for(int j=i; j<array.length - 1; j++){
if(array[j + 1] < array[minIndex]){
minIndex = j + 1;
}
}
swap(array, i, minIndex);
}
}
private static void swap(int[] array, int index1, int index2) {
int temp = array[index1];
array[index1] = array[index2];
array[index2] = temp;
}
}
插入排序法
插入排序法保持数组的前面一部分有序，并不断地把后面无序的数据插入到前面有序的一部分，同时仍然保持前面的数据有序。这里仍然用整数数组的升序排序来说明其原理：首先假设数组第1个数据为有序数组（虽然只有1个数据，但那肯定是有序的数组），然后将第2个数据与前面1个数据对比，如果第2个数据比前一个小，就先把第2个数据保存到临时变量中，然后依次往前循环，与前面的每个数据（第一次循环只有1个）作比较，如果前面的数据比临时变量大，就把前面的数据往后移1个位置（复制到后一个位置上），直到遇到比临时变量小的数据，把临时变量插入到比它小的那个数据的后面。如果对比到了下标为0的数据之后仍然没有比临时变量小的数据，就直接把临时变量插入到下标为0的位置上。用插入排序法进行逆序排序的情况下，第1次循环需要3次复制（复制出临时变量，把有序部分后移的时候也要复制，再把临时变量复制到正确的位置），第2次循环需要4次复制……第N-1次循环（因为是从第2个数据开始，所以只有N-1次）需要N+1次复制，一共(N^2+3N+3)/2次复制。如果数组中的数据是随机的，则平均需要(N^2+3N+3)/4次复制。同样，用大O表示法的时候，把常数3与3/4去掉（可以看作(N^2+3N)/4 + 3/4），再忽略掉3N，可以认为插入排序需要O(N^2)级别时间。但是一次复制与一次交换消耗的时间不同（一次交换有3次复制），所以插入排序法比冒泡排序法快得多，比选择排序略快。
以下代码中添加了插入排序法insertionSort：
package dsaa.array;
/**
* @(#)ArrayUtil.java 2008-12-25 下午08:44:46
*
* @author Qiu Maoyuan
* Array Util
*/
public class ArrayUtil {
public static void bubbleSort(int[] array){
for(int i=0; i<array.length - 1; i++){
for(int j=0; j<array.length - i - 1; j++){
if(array[j]>array[j + 1]){
swap(array, j, j + 1);
}
}
}
}
public static void selectionSort(int[] array){
for(int i=0; i<array.length - 1; i++){
int minIndex = i;
for(int j=i; j<array.length - 1; j++){
if(array[j + 1] < array[minIndex]){
minIndex = j + 1;
}
}
swap(array, i, minIndex);
}
}
public static void insertionSort(int[] array){
for(int i=1; i<array.length; i++){
if(array[i]<array[i - 1]){
int temp = array[i];
int j = i - 1;
while(j>=0 && temp<array[j]){
array[j + 1] = array[j];
j--;
}
array[j + 1] = temp;
}
}
}
private static void swap(int[] array, int index1, int index2) {
int temp = array[index1];
array[index1] = array[index2];
array[index2] = temp;
}
}
奇偶排序法
奇偶排序法的思路是在数组中重复两趟扫描。第一趟扫描选择所有的数据项对，a[j]和a[j+1]，j是奇数(j=1, 3, 5……)。如果它们的关键字的值次序颠倒，就交换它们。第二趟扫描对所有的偶数数据项进行同样的操作(j=2, 4, 6……)。重复进行这样两趟的排序直到数组全部有序。
下面的代码是我原来的写法：
public void oddEvenSort(int[] array){
for (int i = 0; i < array.length; i += 2){
int j = 0;
scan(array, j);
j = 1;
scan(array, j);
}
}
private void scan(int[] array, int j) {
while (j < array.length - 1){
if (array[j] > array[j + 1]){
swap(array, j, j + 1);
}
j += 2;
}
}
private static void swap(int[] array, int index1, int index2) {
int temp = array[index1];
array[index1] = array[index2];
array[index2] = temp;
}
后来有朋友提出建议，我小小的改动了一下，对随机数组排序的效率略有提高：
public static void oddEvenSort(int[] array) {
boolean unsorted = true;
while (unsorted) {
unsorted = false;
int i = 1;
boolean oddUnsorted = scan(array, i);
i = 0;
boolean evenUnsorted = scan(array, i);
unsorted = oddUnsorted || evenUnsorted;
}
}
private static boolean scan(int[] array, int i) {
boolean unsorted = false;
while (i < array.length - 1) {
if (array[i] > array[i + 1]) {
swap(array, i, i + 1);
unsorted = true;
}
i += 2;
}
return unsorted;
}
private static void swap(int[] array, int index1, int index2) {
int temp = array[index1];
array[index1] = array[index2];
array[index2] = temp;
}
和冒泡排序法一样，奇偶排序的时间复杂度为O(N^2)。
《Java数据结构和算法》 写道
奇偶排序实际上在多处理器环境中很有用，处理器可以分别同时处理每一个奇数对，然后又同时处理偶数对。因为奇数对是彼此独立的，每一刻都可以用不同的处理器比较和交换。这样可以非常快速地排序。
以上四种算法的运行效率我在本机上测试了一下，结果如下：
冒泡排序法对长度为1万的数组进行逆序排序，平均花费时间0.235秒；对随机数组进行升序排序，平均花费时间0.329秒。。。。这个这个。。。
选择排序法对长度为1万的数组进行逆序排序，平均花费时间0.188秒；对随机数组进行升序排序，平均花费时间0.218秒…………
插入排序法对长度为1万的数组进行逆序排序，平均花费时间0.141秒；对随机数组进行升序排序，平均花费时间0.078秒。（这回才正常，相当奇怪呀……我写的算法应该没有错吧，为什么冒泡排序和选择排序在逆序排序的时候比较快呢？？
具体原因暂时先参考问答频道这里http://www.iteye.com/problems/9236）
奇偶排序法对长度为1万的数组进行逆序排序，平均花费时间0.203秒；对随机数组进行升序排序，平均花费时间0.266秒。。。
===================2008-12-29===================
昨天复习了链表一章，增加了一个表插入排序法，同时用泛型改写了一下以前的各排序算法。测试结果是：
引用
冒泡-随机:1.265
冒泡-逆序:1.422
选择-随机:0.969
选择-逆序:0.86
插入-随机:0.735
插入-逆序:1.375
表插入-随机:0.484
表插入-逆序:0.641
冒泡-逆序:1.422
选择-随机:0.969
选择-逆序:0.86
插入-随机:0.735
插入-逆序:1.375
表插入-随机:0.484
表插入-逆序:0.641
附上时间测试代码：
import java.util.Random;
public class ArrayUtil {
/**
* 冒泡排序
* @param array
*/
public static <T extends Comparable<? super T>> void bubbleSort(T[] array){
for(int i=0; i<array.length - 1; i++){
for(int j=0; j<array.length - i - 1; j++){
if(array[j].compareTo(array[j + 1])>0){
swap(array, j, j + 1);
}
}
}
}
/**
* 选择排序
* @param array
*/
public static <T extends Comparable<? super T>> void selectionSort(T[] array){
for(int i=0; i<array.length - 1; i++){
int minIndex = i;
for(int j=i; j<array.length - 1; j++){
if(array[j + 1].compareTo(array[minIndex])<0){
minIndex = j + 1;
}
}
swap(array, i, minIndex);
}
}
/**
* 插入排序
* @param array
*/
public static <T extends Comparable<? super T>> void insertionSort(T[] array){
for(int i=1; i<array.length; i++){
if(array[i].compareTo(array[i - 1])<0){
T temp = array[i];
int j = i - 1;
while(j>=0 && temp.compareTo(array[j])<0){
array[j + 1] = array[j];
j--;
}
array[j + 1] = temp;
}
}
}
/**
* 奇偶排序
* @param array
*/
public static <T extends Comparable<? super T>> void oddEvenSort(T[] array) {
boolean unsorted = true;
while (unsorted) {
unsorted = false;
int i = 1;
boolean oddUnsorted = scan(array, i);
i = 0;
boolean evenUnsorted = scan(array, i);
unsorted = oddUnsorted || evenUnsorted;
}
}
private static <T extends Comparable<? super T>> boolean scan(T[] array, int i) {
boolean unsorted = false;
while (i < array.length - 1) {
if (array[i].compareTo(array[i + 1])>0) {
swap(array, i, i + 1);
unsorted = true;
}
i += 2;
}
return unsorted;
}
private static <T extends Comparable<? super T>> void swap
(T[] array, int index1, int index2) {
T temp = array[index1];
array[index1] = array[index2];
array[index2] = temp;
}
/**
* 表插入排序法
* @param <T>
* @param array
*/
@SuppressWarnings("unchecked")
public static <T extends Comparable<? super T>> void listInsertionSort(T[] array){
SortedLinkList<?> linkList = new SortedLinkList(array);
T[] newArray = (T[])new Comparable[array.length];
for(int i=0; i<newArray.length; i++){
newArray[i] = (T)linkList.remove();
}
array = newArray;
}
public static void main(String[] args){
Integer[] array = new Integer[10000];
generateRandomArray(array);
long b = System.currentTimeMillis();
ArrayUtil.bubbleSort(array);
long e = System.currentTimeMillis();
System.out.println("冒泡-随机:" + (e - b)/1000.0);
generateContradictoryArray(array);
b = System.currentTimeMillis();
ArrayUtil.bubbleSort(array);
e = System.currentTimeMillis();
System.out.println("冒泡-逆序:" + (e - b)/1000.0);
generateRandomArray(array);
b = System.currentTimeMillis();
ArrayUtil.selectionSort(array);
e = System.currentTimeMillis();
System.out.println("选择-随机:" + (e - b)/1000.0);
generateContradictoryArray(array);
b = System.currentTimeMillis();
ArrayUtil.selectionSort(array);
e = System.currentTimeMillis();
System.out.println("选择-逆序:" + (e - b)/1000.0);
generateRandomArray(array);
b = System.currentTimeMillis();
ArrayUtil.insertionSort(array);
e = System.currentTimeMillis();
System.out.println("插入-随机:" + (e - b)/1000.0);
generateContradictoryArray(array);
b = System.currentTimeMillis();
ArrayUtil.insertionSort(array);
e = System.currentTimeMillis();
System.out.println("插入-逆序:" + (e - b)/1000.0);
generateRandomArray(array);
b = System.currentTimeMillis();
ArrayUtil.listInsertionSort(array);
e = System.currentTimeMillis();
System.out.println("表插入-随机:" + (e - b)/1000.0);
generateContradictoryArray(array);
b = System.currentTimeMillis();
ArrayUtil.listInsertionSort(array);
e = System.currentTimeMillis();
System.out.println("表插入-逆序:" + (e - b)/1000.0);
}
private static void generateContradictoryArray(Integer[] array) {
for(int i=0; i<array.length; i++){
array[i] = array.length - i;
}
}
private static void generateRandomArray(Integer[] array) {
Random random = new Random();
for(int i=0; i<array.length; ){
int item = random.nextInt(10000);
int j;
if(i==0) array[i]=item;
for(j=0; j<i; ){
if(array[j]==item) break;
j++;
}
if(j==i){
array[i] = item;
i++;
}
}
}
}
class SortedLinkList<E extends Comparable<E>> {
private Link first;
public SortedLinkList() {
}
public SortedLinkList(E[] array) {
for (E element : array) {
add(element);
}
}
public void add(E value) {
Link newElement = new Link(value);
if (isEmpty()) {
first = newElement;
} else {
Link current = first;
Link previous = null;
while (!endOfLink(current) && current.element.compareTo(value) >= 0) {
previous = current;
current = current.next;
}
if (!endOfLink(current)) {
newElement.next = current;
}
if (current == first)
first = newElement;
else
previous.next = newElement;
}
}
public E getFirst() {
if (isEmpty())
throw new IllegalStateException("Linklist is empty");
return first.element;
}
public boolean isEmpty() {
return first == null;
}
public E remove() {
E value = getFirst();
first = first.next;
return value;
}
public boolean delete(E element) {
if (isEmpty())
return false;
Link current = first;
Link previous = first;
while (!element.equals(current.element)) {
if (endOfLink(current.next)) {
return false;
} else {
previous = current;
current = current.next;
}
}
if (current == first)
first = first.next;
else
previous.next = current.next;
return true;
}
private boolean endOfLink(Link link) {
return link == null;
}
@Override
public String toString() {
StringBuilder buffer = new StringBuilder();
Link current = first;
while (current != null) {
buffer.append(current.toString());
current = current.next;
}
return buffer.toString();
}
private class Link {
private E element;
private Link next;
public Link(E element) {
this.element = element;
}
@Override
public String toString() {
return "[" + element.toString() + "]";
}
}
}
- SimpleSort.zip (16.5 KB)
- 下载次数: 52
分享到：
发表评论
-
《Java数据结构和算法》学习笔记(6)——高级排序
2009-01-02 15:07 0希尔排序 希尔排序是插入排序法的改进。 插入排序在最坏的情况 ... -
《Java数据结构和算法》学习笔记(5)——递归 归并排序
2009-01-01 18:53 3037每篇笔记都会附上随书的Applet演示程序，有算法看不明白的， ... -
《Java数据结构和算法》学习笔记(4)——链表
2008-12-28 17:32 2268每篇笔记都会附上随书的Applet演示程序，有算法看不明白的， ... -
《Java数据结构和算法》学习笔记(3)——栈和队列
2008-12-27 03:40 2619每篇笔记都会附上随书的Applet演示程序，有算法看不明白的， ... -
《Java数据结构和算法》学习笔记(1)——数组 二分法 大O表示法
2008-12-25 16:14 4531马上要自考了，其中有 ...
相关推荐
中软国际培训的学习笔记，很值得参考。学习java数据结构很有必要看看
Java数据结构和算法学习笔记,对于爱好Java人员来说，再好不过了
这是我从B站上看韩老师讲的数据结构与算法后整理的笔记 代码经过运行，欢迎批评指正 有些地方我感觉还是挺难的 大都经过我自己的语言进行描述，韩老师中期的表达可能或多或少也影响可阅读性，望先生们见谅
Java数据结构和算法 Java数据结构和算法 Java数据结构和算法 Java数据结构和算法 Java数据结构和算法 Java数据结构和算法 Java数据结构和算法 Java数据结构和算法
Java数据结构与算法学习笔记之排序 冒泡排序,选择排序,插入排序,希尔排序, 归并排序, 快速排序.
《Java数据结构和算法》（第2版）介绍了计算机编程中使用的数据结构和算法，对于在计算机应用中如何操作和管理数据以取得最优性能提供了深入浅出的讲解。全书共分为15章，分别讲述了基本概念、数组、简单排序、堆和...
sgg数据结构和算法笔记
数据结构、算法与应用——C++语言描述.rar
java 数据结构和算法， 排序算法， 数组，链表，二叉树
包含了各种数据结构和算法（java）的实现方式和详解（图解），包括单双链表、环形链表（约瑟夫问题）、栈、后缀表达式、中缀表达式转后缀表达式、迷宫问题、八大排序算法、多种查找算法、哈希表、二叉树实现以及操作...
《Java数据结构和算法》(第2版)介绍了计算机编程中使用的数据结构和算法，对于在计算机应用中如何操作和管理数据以取得最优性能提供了深入浅出的讲解。全书共分为15章，分别讲述了基本概念、数组、简单排序、堆和...
数据结构与算法分析——Java语言描述.pdf
介绍了计算机编程中使用的...《Java数据结构和算法》(第2版)提供了学完一门编程语言后进一步需要知道的知识。本书所涵盖的内容通常作为大学或学院中计算机系二年级的课程，在学生掌握了编程的基础后才开始本书的学习。
数据结构与算法分析学习笔记数据结构与算法分析学习笔记数据结构与算法分析学习笔记数据结构与算法分析学习笔记数据结构与算法分析学习笔记
数据结构和算法学习笔记
这本书是用java讲数据结构和排序算法的，全书只有44页，但是讲的内容很不错，推荐学习或者复习数据结构的童鞋下在看看！