算法笔记（第一部分）-- 排序之名词

关于算法的笔记应该三年前就开始总结，哎，拖到现在。最近在公司上班闲着无聊，开始重新看算法中的各种排序，发现三年前不能领悟的东西，现在慢慢地开始有些懂了。为了应付以后的各种面试，准备对比较常用的一些排序做一些傻瓜式的整理。

排序的关键字：
1. 时间复杂度：整个排序算法运行所需要的时间。
2. 空间复杂度：排序算法运行过程中所需额外空间。
3. 稳定性：若待排序的序列中有大小相同的两个数，若整个排序过程中不存在两数次序交换的可能性，则该排序算法是稳定的。
4. In-place：算法使用的额外存储空间是常数级的。

由‘简’入‘难’，第一篇介绍最基本的冒泡排序-Bubble Sort

附使用到的函数：

public void swap(int[] data, int i, int j){
            if(i!=j){
                  data[i] = data[i]+data[j];
                  data[j] = data[i]-data[j];
                  data[i] = data[i]-data[j];
           }
      }

评论

6 楼 lenky0401 2008-09-07  

总得来收不使用临时变量有三种方法交换两整数
一
a=a^b;
b=a^b;
a=a^b;
二
a = a + b;
    b = a - b;
    a = a - b;
三
a = a - b;
    b = a + b;
    a = b - a;

5 楼 anbutu 2008-09-07  

我觉得为了节省那么一点空间把交换写成这个样子是得不偿失。不但会增加算法的时间复杂度，而且使算法失去了通用行，这个算法对整数适用，但对于一些其他的数据类型就。。。

4 楼 lenky0401 2008-09-07  

额 不使用临时变量交换两数据 还有异或的方法

3 楼 SCYForce 2008-09-04  

引用

看不懂

在我的这个Swap函数中，因为它的功能是不使用临时变量对数组中的两个数进行交换，当i与j相等时，会出错。

简单的交换原理有a和b两个数：
a = a + b;
b = a + b - b = a;
a = a + b -a = b;

交换完成。

2 楼 wm11314 2008-09-03  

交换  

1 楼 hlily2005 2008-09-02  

看不懂