排序（链表）

首先说一下程序运行时间的计算：
一般法则：
法则1—for循环：
一次 for 循环的运行时间至多是该 for 循环内语句（包括测试）的运行时间乘以迭代次数。
法则2–嵌套的for循环：
自内向外分析，在一组嵌套循环内部的一条语句总的运行时间为该语句的运行时间乘以该组所有的 for 循环的大小的乘积。
法则3–顺序语句：
将各个语句的运行时间求和即可（其中的最大值就是所得的运行时间）。
法则4–if/else语句：
一个 if/else 语句的运行时间从不超过判断的时间加上两种情况中运行时间较长者的总的运行时间。

举个例子：
计算下面这个式子：

int
sum(int n)
{
	    int i,ans;
/*1*/	for(i = 1; i <= n; i++)
/*2*/		ans += i*i;
/*3*/	return ans;
}

对于第一行：初始化占用1个时间单元，比较占用 N+1 个时间单元（ N 次判断是否小于，1次判断是否等于），以及自增占用 N个时间单元，共 2N+2 个时间单元；
对于第二行：1次乘法 + 一次加法 + 一次赋值 ，共 3N 个时间单元；
对于第三行：忽略返回值占用的时间；
综上，得到的总的时间是 5N+2 。因此其时间复杂度为Ｏ(N).

再看看下面这个例子：

int
MaxSubsequenceSum(const int A[], int N)
{
	int ThisSum, MaxSum, i, j, k;
/*1*/	MaxSum = 0;
/*2*/	for( i = 0; i < N; i++)
/*3*/		for( j = i; j　< N; j++){
/*4*/			ThisSum = 0;
/*5*/			for( k = i; k <= j; k++)
/*6*/				ThisSum += A[k];
/*7*/			if( ThisSum > MaxSum)
/*8*/				MaxSum = ThisSum;
			}	
	return MaxSum;
}

第一眼看上去，就是一个三重嵌套，第一个循环大小为 N ，第二个循环的大小为 N-i（可能为N，也可能很小。但必须假设最坏的情况，假设它为N）, 第三个循环的大小为 j - i + 1, 我们也假设它的大小为 N，对于7和8他们是一个两层嵌套，时间为O(N＾２)，别的忽略不计， 则总时间为O(N^3)。
我们精确分析一下：
自内向外，第二层和第三层嵌套的总时间为：(1 + N - i）(N - i) / 2; 再加上第一层，即 i = 0 开始到 i = N，对 (1 + N - i）(N - i) / 2 求和，得到 ( N^3 + 3N＾２+2N）/ 6.

对一个链表进行排序：
1. 冒泡排序（针对时间复杂度和空间复杂度要求不高的问题）

时间复杂度O(N^2)
基本思想：每次比较两个相邻的元素，如果它们的顺序错误就把他们交换过来

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */


struct ListNode* sortList(struct ListNode* head){
    struct ListNode* newHead = head;
    struct ListNode* movpt;
    struct ListNode* fwd;
    int  length = 0;
    if(head == NULL || head->next == NULL)
        return head;
    while(head){
        head = head->next;
        length++;   
    }
    head = newHead;
    fwd = head->next;
    for(int i = 0; i < length - 1; i++){
        movpt = head;
        fwd = movpt->next;
        for(int j = i; j < length - 1 ; j++){
            if(head->val > fwd->val){
                int temp = head->val;
                head->val = fwd->val;
                fwd->val = temp;
            }
            fwd = fwd->next;
        }
        head = movpt->next;
    } 
    return newHead;
}

2. 快速排序
待续…