java Data Structural / shujujiegou / paixusuanfa / paixu

 

http://panthema.net/2013/sound-of-sorting/     

The Sound of Sorting - "Audibilization" and Visualization of Sorting Algorithms TalkBox Gravatar Timo: I don't see much point in the input types, you can check out the code and try these yourself. One can add many different types of inputs. There is no release schedule. Releases are quite a hassle to make, but once enough additional algorithms are added in the git repo, I'll make new binaries. Gravatar mgutt: Could you add ascending/descending cubic and quintic input types? When do you plan to push to a new downloadable executable? Just wondering. Gravatar Timo: @Dan: thanks for the bug report. It's fixed in git now, the number of radix rounds needed was too low for n=4^k. Gravatar Dan: Radix sort LSD gives incorrect results every time with array size 12 and shuffled cubic or quintic as source on linux version. Gravatar Timo: Yes, well, I don't have Windows 8.1. Gravatar mgutt: I found something about high-resolution timers for Windows 8.1 and later. Would be great to have the < 1 ms resolution. Gravatar Timo: @mgutt: that sounds like a very good idea. I'll replace the "Random" button with Shuffle/Reset in the next version. @Page: Execution time analysis of sorting algorithms is really difficult. It depends on many parameters like hardware, input and implementation. It is really outside the scope of SoS, which is primarily an educational tool. Gravatar Page: Have you done any kind of comparison statistics of total computing time vs array accesses/comparisons? Those would be pretty cool. Gravatar mgutt: It would be nice if the "Reset" button simply reverted the array to its presorted state, not mix the elements. That way, it is possible to see different sorting algorithms being performed on the exact same array. To mix the array, you could add a "Shuffle" button. Gravatar mgutt: Please add Timsort, Stooge sort, and slow sort to the demo program. This program is so amazing to me. Gravatar Timo: TimSort is already implemented on git. Wouldn't KraaySort violate a patent? I can't find any implementation. Gravatar mr.k.s.a: hi https://github.com/gfx/cpp-TimSort Gravatar kone: implement kraaysort link1 link2 link3 link4 Gravatar Sampo Syreeni: The sound in that andrut video has clearly been done by modulating the cutoff point of an analog-like filter, over a toothy waveform. Maybe a fixed high saw waveform or something like that. I might be wrong, but the filter might also be the rarest one in analog synthesis: the band reject one. Gravatar Alessandro: That would be amazing if I were able to manually specify the input: I would definitely use this to try making a song!!! :D Gravatar Timo: Upon your requests: added TimSort, Slow Sort and Stooge Sort (see github). Videos about them are also on Youtube now. Cheers, Timo Gravatar quchen: Slowsort is missing! It's a highly entertaining variant of mergesort, described in this paper: http://www.cse.ohio-state.edu/~yusu/courses/780/pessimal.pdf Gravatar ahmet: yes yes timsort pls Gravatar Shintaro: Hi! Here some links to an other project we did in 2010. http://sourceforge.net/p/algorhythmics/code/288/tree/algorhythmicSorting/ https://vimeo.com/42353230 Gravatar Keith: Would love to see Timsort too: http://en.wikipedia.org/wiki/Timsort Posted on 2013-05-22, last updated 2013-11-26 by Timo Bingmann at Permlink.

sound-of-sorting-0.6-win32.zip 

http://dl.iteye.com/topics/download/a4449a92-af61-32bb-bab4-76c9cfeaa49e

程序猿的世界我们不懂 15种排序算法演示

http://v.gamersky.com/201404/350555.shtml

1、选择排序

2、插入排序

3、快速排序

4、归并排序

5、堆排序

6、基数排序

7、是C++标准库自带的一个排序方法，实质上就是快速排序

8、同样是C++的一个排序法

9、希尔排序

10、冒泡排序

11、双向冒泡排序，是10的变种

12、地精排序

13、双调排序

14、严格来说它不是一种排序法，它只是把元素随意打乱看是否有序，若否则再次打乱，理论上时间复杂度是无限的，因此我觉得它不能算是排序法，没有第15，总共只有14种排序法

15、最后一个是穷举法吗，就是把所有可能的排列都列举一遍，找出与条件相符的。 

 

 

http://jiangzhengjun.iteye.com/blog/pdf

http://jiangzhengjun.iteye.com/blog/547734

http://jiangzhengjun.iteye.com/blog/547735

 

排序算法分析与实现
查看目录

 

• 1. 数据结构
  • 1.1 常用排序算法分析与实现（一）（Java版）
  • 1.2 常用排序算法分析与实现（二）（Java版）

 

申明：  排序算法思想来自互联网，代码自己实现，仅供参考。

• 插入排序

直接插入排序、希尔排序

• 选择排序

简单选择排序、堆排序

• 交换排序

冒泡排序、快速排序

• 归并排序

• 基数排序

排序基类

 

时间复杂度与空间复杂度对比表

 

 

http://shenyu.iteye.com

 

枚举算法

有N(N>=3)位同学去照相，每次照三个同学,共可照出多少张不同的照片?每张照片都是谁?

 

package com.lindows.test;

public class CountNum {

		public static void main(String[] args)
		{
			int total =4;		
			for(int i =0;i<= total-3;i++)
			{
				for(int j =i+1;j<= total-2;j++)
				{
					for(int k =j+1;k<= total-1;k++)
					{
						System.out.println(print(i)+":"+print(j)+":"+print(k));
					}
				}
			}
		}
		
		public static char print(int num)
		{		
			return (char)((int)'A' + num);
		}



}

asdfsfa

?

冒泡法排序示例
文件：Sort.java  
内容：  
public class Sort
{
public static void main (String[] args) {
??System.out.print("以下有10个数: 5,2,3,6,8,7,1,0,9,4\n");
??int[] num = new int[]{5,2,3,6,8,7,1,0,9,4};
??//boolean isChange = false;
??for(int i=0;i<9;i++)
??{
?? //isChange = false;
?? for(int j=0;j<9;j++)
?? {
????if(num[j]>num[j+1])
????{
???? int temp = num[j];
???? num[j] = num[j+1];
???? num[j+1] = temp;
???? //isChange = true;???? 
????}
?? }
?? //System.out.print(num[i-1]);
??}
??System.out.print("\n冒泡排序后为: ");
??for(int k=0;k<10;k++)
?? System.out.print(num[k]+ ",");
}??
}
结果：
以下有10个数: 5,2,3,6,8,7,1,0,9,4
冒泡排序后为: 0,1,2,3,4,5,6,7,8,9,

 

 

 

冒泡，选择，插入排序 java版

http://hpjianhua.iteye.com/blog/846021

公共代码交换两个数的方法： 

/**
 * 交换两个数的方法
 * @param data 交换的数组
 * @param i 位置i的数组下标
 * @param j 位置j的数组下标
 */
public   static   void  swap( int [] data,  int  i, int  j){
    //  当只有是不同一位置的两个数才进行交换
    if (i!=j){
         int  temp =  0 ;
         temp = data[j];
         data[j] = data[i];
         data[i] = temp;
    }
}

1.插入排序： 
思想：每步将一个待排序的对象，按其关键码大小，插入到前面已经排好序的一组对象的适当位置上，直到对象全部插入为止。 

代码实现： 

/**
 * 插入排序算法
 * 每进行一次排序，就需要将要比较的数与有序的序列进行一一对比
 * @param data
 * @param n
 */
public   static   void  insertion( int [] data,  int  n){
    for ( int  i =  0  ; i < data.length;i++){
        for ( int  j =  0  ; j<i;j++){
            if (data[i]<data[j]){
                swap(data,i,j);
            }
        }
        System.out.println("第" +i+ "趟：" +Arrays.toString(data));
    }
}

2.选择排序： 
思路简单：每经过一趟比较就找出一个最小值，与待排序列最前面的位置互换即可。 
——首先，在n个记录中选择最小者放到r[1]位置；然后，从剩余的n-1个记录中选择最小者放到r[2]位置；…如此进行下去，直到全部有序为止。 
优点：实现简单 
缺点：每趟只能确定一个元素，表长为n时需要n-1趟 
前提：顺序存储结构 

/**
 * 选择排序算法
 * 每经过一趟比较就找出一个最小值，与待排序列最前面的位置互换即可
 * @param data
 * @param n
 */
public   static   void  select( int [] data,  int  n){
    for ( int  i =  0  ; i < data.length; i++){
        int  min = i;
        for  ( int  j = i+ 1 ; j<data.length; j++){
            if (data[j]<data[min]){
                min = j;
            }
        }
        if (i!=min){
            swap(data,min,i);
        }
        System.out.println("第" +i+ "趟：" +Arrays.toString(data));
    }
}

冒泡排序： 
基本思路：每趟不断将记录两两比较，并按“前小后大”（或“前大后小”）规则交换。(逆序则交换) 
优点：每趟结束时，不仅能挤出一个最大值到最后面位置，还能同时部分理顺其他元素；一旦下趟没有交换发生，还可以提前结束排序。 
前提：顺序存储结构 

/**
 * 冒泡排序算法
 * 每次都是进行相邻两个数的比较，每比较一次，比较的个数就变少一个
 * @param data
 * @param n
 */
public   static   void  bubble( int [] data,  int  n){
    for ( int  i =  1 ; i <=data.length; i++){
        for ( int  j =  0 ; j<(data.length-i);j++){
            if (data[j]>data[j+ 1 ]){
                swap(data,j,j+1 );
            }
        }
        System.out.println("第" +i+ "趟：" +Arrays.toString(data));
    }
}

 

http://yiyickf.iteye.com/blog/1047010

http://www.cppblog.com/guogangj/archive/2009/11/13/100876.html

排序算法java版：冒泡排序、简单选择排序、直接插入排序、折半插入排序、希尔排序、堆排序、归并排序、快速排序

先推荐一篇关于排序算法的文章：http://www.cppblog.com/guogangj/archive/2009/11/13/100876.html

本文思路部分来源于上篇文章，但测得的结果似乎不大相同，不知是因为java的缘故还是因为我算法的缘故，欢迎拍砖。

复习排序，顺便比下各种算法的速度，榜单如下：

1、冒泡排序

2、简单选择排序

3、直接插入排序

4、折半插入排序

5、希尔排序

6、堆排序

7、归并排序

8、快速排序

当然这是慢速排行，哈哈~~

 

 

直接上图：单位毫秒

 

数量	冒泡排序	简单选择排序	直接插入排序	折半插入排序	希尔排序	堆排序	归并排序	快速排序
10000 个	1578	1250	672	250	0	15	16	0
15000 个	3453	2765	1563	531	16	15	16	0
20000 个	6140	4547	2453	828	16	16	15	16
25000 个	10079	7171	3969	1313	31	16	15	16
30000 个	14641	10313	5578	1906	31	31	16	31
35000 个	20141	14328	7890	2563	31	31	32	15
40000 个	25766	18359	10094	3422	47	31	31	32
45000 个	32469	24063	13062	4359	47	47	31	47

 

 

 

end