精华内容
下载资源
问答
  • 链表插入排序

    2017-02-21 17:42:49
    链表插入排序 题目描述:用插入排序法对链表进行排序 given 1->3->2->0->NULL, return 0->1->2->3->NULL 算法描述: 算法一:将题目中给出的链表数据结构转换为C++标准库中的标准list数据结构,调用c++标准库中...

    链表插入排序
    题目描述:用插入排序法对链表进行排序
    given 1->3->2->0->NULL, return 0->1->2->3->NULL
    算法描述:
    算法一:将题目中给出的链表数据结构转换为C++标准库中的标准list数据结构,调用c++标准库中的list算法进行排序即可完成
    算法二:将题目中给出的链表数据结构转换为vrector,对vector进行插入排序,插入排序的算法如下所示:

        vector<int> insertSort(vector<int> a, int length)
        {
            int key,i;
            for(int j = 1;j<length;j++)
            {
                key = a[j];
                i = j;
                while(i>0 && a[i-1] > key)
                {
                    a[i] = a[i-1];
                    i = i-1;
                }
                a[i] = key;
            }
            return a;
        }

    插入排序的整体思想类似于玩扑克牌游戏摸牌阶段整理扑克牌顺序的思想。再对排序好的vector创建为list。创建list的代码如下:

        ListNode* createList(vector<int>a, int length)
        {
            ListNode * head, *tail, *mid;
            head = tail = NULL;
            int i = 0;
            while (i < length)
            {
                mid = new ListNode(-1);
                mid->val = a[i];
                mid->next = NULL;
                if (head == NULL)
                {
                    head = mid;
                }
                else
                {
                    tail->next = mid;
                }
                tail = mid;
                i++;
            }
            return head;
        }

    则解决该问题的整体代码如下:

    /**
     * Definition of ListNode
     * class ListNode {
     * public:
     *     int val;
     *     ListNode *next;
     *     ListNode(int val) {
     *         this->val = val;
     *         this->next = NULL;
     *     }
     * }
     */
    class Solution {
    public:
        /**
         * @param head: The first node of linked list.
         * @return: The head of linked list.
         */
        ListNode *insertionSortList(ListNode *head)
        {
            // write your code here
            //step one: List 2 vector
            vector<int> raw_data;
            vector<int> mid_data;
            ListNode* result;
            while(head != NULL)
            {
                raw_data.push_back(head->val);
                head = head ->next;
            }
            //step two: sorting
            mid_data = insertSort(raw_data,raw_data.size());
            //step three: vector 2 list
            result = createList(mid_data,raw_data.size());
            return result;    
        }
        vector<int> insertSort(vector<int> a, int length)
        {
            int key,i;
            for(int j = 1;j<length;j++)
            {
                key = a[j];
                i = j;
                while(i>0 && a[i-1] > key)
                {
                    a[i] = a[i-1];
                    i = i-1;
                }
                a[i] = key;
            }
            return a;
        }
        ListNode* createList(vector<int>a, int length)
        {
            ListNode * head, *tail, *mid;
            head = tail = NULL;
            int i = 0;
            while (i < length)
            {
                mid = new ListNode(-1);
                mid->val = a[i];
                mid->next = NULL;
                if (head == NULL)
                {
                    head = mid;
                }
                else
                {
                    tail->next = mid;
                }
                tail = mid;
                i++;
            }
            return head;
        }
    };
    展开全文
  • 主要介绍了JavaScript实现链表插入排序和链表归并排序,较为详细的分析了插入排序和归并排序,对于学习JavaScript数据结构具有一定参考借鉴价值,需要的朋友可以参考下。
  • 插入排序,包括普通插入排序、折半插入排序、链表插入排序、希尔排序的描述

    插入排序,对数据集D{D1, D2, D3,.......DN},对每个数据按需要的排序方向,找到应该在的位置;更直白的说,保证数据{D[1]-D[x-1]}的有序,是寻找数据DX应该在的位置时的前提,即{D[1]-D[x-1]}有序情况下,再去寻找D[x]应该在{D[1]-D[x]}之中的位置,直到保证全部数据的有序。

    相比冒泡排序和选择排序,插入排序可能不是特别的直观能想到。


    1、直接插入排序:

    直接插入排序就是插入排序最直观的实现,其思想详见程序及其注释,还算比较清楚。

    insert.h(类声明):

    #include <vector>
    
    template<class T> class insertsort {
        std::vector<T> data;
    public:
        insertsort(T *data, int size);
        insertsort(std::vector<T> _data);
        ~insertsort(){data.clear();}
        void isort();
        void show(bool direct);
    };

    insert_func.h(类实现):

    #include "insert.h"
    #include <iostream>
    
    
    
    
    template<class T> insertsort<T>::insertsort (T *_data, int size) {
    	for (int i = 0; i < size; i++) {
    		data.push_back(_data[i]);
    	}
    	isort();
    }
    
    
    template<class T> insertsort<T>::insertsort (std::vector<T> _data) {
    	data = _data;
    	isort();
    }
    
    
    //普通插入排序, 以希望从小到大方向排序为例, 就是当发现索引i处数据比他后面的数据大即违背从小到大方向时, 即在[0, i]之中找到i+1索引处数据应该在的位置, 寻找方式是从i-1开始依次向左移位依次比较, 如仍比该数据大则做原数据移位(data[j + 1] = data[j]), 直到找到不比这个数据大的索引j, 把这个数据替换到j处
    //可见, 插入排序就是通过保持从头到当前索引i的数据data[0, i]有序, 如发现索引i+1的数据违背排序时, 顺序的为这个数据找到它在[0, i]中应该在的位置. 
    //进而得出, 如果原数据就是有序且正序的, 那么时间复杂度就是N-1->O(N)
    //如果原数据是有序且逆序的, 那么时间复杂度1+2+3+...(n-1) = n*(n-1)/2->O(N*N)了.
    //普通插入排序的平均时间复杂度认为是O(N*N)
    //普通插入排序的改进应从两个角度进行: 
    //1. 减少寻找索引i+1数据在[0, i]应该在的位置的比较次数(折半插入排序)
    //2. 减少寻找索引i+1数据在[0, i]应该在的位置的原数据移位次数(改造为链表的普通插入排序)
    //3. 同时减少1和2(希尔排序)
    template<class T> void insertsort<T>::isort () {
    	for (int i = 1; i < data.size(); i++) {
    		T curdata = data[i];
    		int j = i - 1;
    		for (; j >= 0; j--) {
    			if (data[j] <= curdata) {
    				break;
    			}
    
    
    			data[j + 1] = data[j];
    		}
    		data[j + 1] = curdata;
    	}
    }
    
    
    template<class T> void insertsort<T>::show (bool direct) {
    	if (direct) {
    		for (int i = 0; i < data.size(); i++) {
    			std::cout << data[i];
    			if (i != data.size() - 1) {
    				std::cout << ", ";
    			}
    		}
    	} else {
    		for (int i = data.size() - 1; i >= 0; i--) {
    			std::cout << data[i];
    			if (i != 0) {
    				std::cout << ", ";
    			}
    		}
    	}
    	std::cout << std::endl;
    }
    insert.cpp(测试程序):

    #include "insert_func.h"
    #include <stdlib.h>
    
    
    int main () {
    	int *testdata = new int[sizeof(int) * 30];
    	srand((int)time(0));
    	for (int i = 0; i < 30; i++) {
    		testdata[i] = rand() % 100;
    		std::cout << testdata[i] << " ";
    	}
    	std::cout << std::endl;
    	insertsort<int> insertsorter(testdata, 30);
    	insertsorter.show(1);
    	delete []testdata;
    	return 0;
    }
    很明显,如果我们需要从小到大排序,而原始数据是从大到小有序的,可想而知任何一个数据的寻找其位置的过程中,每一次都要比较,然后要移位(data[j] = data[j - 1]),直到比较到data[0],那么时间复杂度就是1 + 2 + 3 + ... + (n-1) = n * (n - 1)/2相当于O(N * N)。

    同样很明显,如果我们需要从小到大排序,而原始数据已经就是从小到大有序的,那么任何一个数据的寻找其位置的过程中,只需要比较一次就发现无需移位了,那么时间复杂度就是1 * (n - 1)相当于O(N)

    可见,插入排序对于原始数据的排序情况非常敏感,越符合需要排序的方向就越快趋近于O(N),否则就越慢趋近于O(N * N)。

    最好:O(N),最坏:O(N * N),平均:O(N * N)

    所以,对于插入排序的改进就要设法让原始数据尽可能符合所需排序的情况,这样可以减少每次的比较和移位。

    2、折半插入排序:

    折半插入排序致力于减少无谓的比较,比如数据[1,10,11,12,13,14,15,16,17,2],当寻找最后一个数据2应该在的位置时,如果从17、16、15、14...最终找到1发现2应该在当前数据10的位置。但事实上在处理数据2的时候,之前的数据是保证已经有序了的,那么完全可以通过二分查找找到2应该在的位置,也就是说减少了很多比较的次数,由O(N)减为O(logN)。

    但是必须注意,在数据2找到它应该在当前数据10之后,折半插入排序依然需要进行O(N)的移位,即10-11、11-12、12-13、.....17-2,最终2-10的数据移位过程,依然不能少。

    所以说,折半插入排序,利用插入排序会保证当前处理数据之前数据集合的有序性,通过二分查找减少了寻找插入位置的复杂度,减少了比较判断的次数,但仍需要依次移位,未减少移位次数。

    insert_binary.h(类声明):

    #include <vector>
    
    template<class T> class insert_binary {
    	std::vector<T> data;
    	int find_insertindex(int range, T curdata);
    	void swap(int i, int j);
    public:
    	insert_binary(T *data, int size);
    	insert_binary(std::vector<T> _data);
    	~insert_binary(){}
    	void ibsort();
    	void show(bool direct);
    };

    insert_binary_fcun.h(类实现):

    #include "insert_binary.h"
    #include <iostream>
    
    
    template<class T> insert_binary<T>::insert_binary (T *_data, int size) {
    	for (int i = 0; i < size; i++) {
    		data.push_back(_data[i]);
    	}
    	ibsort();
    }
    
    template<class T> insert_binary<T>::insert_binary (std::vector<T> _data) {
    	data = _data;
    	ibsort();
    }
    
    template<class T> void insert_binary<T>::swap (int i, int j) {
    	if (i != j) {
    		T tmp = data[i];
    		data[i] = data[j];
    		data[j] = tmp;
    	}
    }
    
    //按从小到大原则, 找到原数据中不比curdata小的第一个数
    template<class T> int insert_binary<T>::find_insertindex (int range, T curdata) {
    //按从小到大原则, 找到原数据中不比curdata小的第一个数
    	int start = 0, end = range;
    	while (start < end) {
    		int mid = (start + end)/2;
    		if (data[mid] == curdata) {
    			return mid + 1;
    		} else if (data[mid] < curdata) {
    			start = mid + 1;
    		} else if (data[mid] > curdata) {
    			end = mid - 1;
    		}
    	}
    
    //比如[1,2,2,3,4,5,6,2], 在发现最后一个2违反升序时, 会找到第一个不比2小的数是从0开始索引为1的2, 后面的移位操作就会把最后的2移位到索引1, 即排序后和排序前相当位置变化,不稳定排序
    //当然同时也能发现, 折半插入排序的不稳定, 是可以在这里通过改造完善的
    	if (data[(start + end)/2] > curdata) {
    		return (start + end)/2;
    	} else {
    		return (start + end)/2 + 1;
    	}
    }
    
    //折半插入排序, 比普通插入排序的变化是, 普通插入排序是一个个移位直到发现应该的插入位置, 再去做原数据移位
    //而折半插入排序是, 通过二分查找发现应该的插入位置, 再去做原数据移位
    //共同点是都需要做最终的原数据移位, 区别是折半插入排序在发现插入位置的过程中, 省去了一些不必要的移位比较(O(N)变为O(logN))
    //相比普通插入排序, 折半插入排序是不稳定的, 原因见insert_binary内的注释, 但可以改造为稳定
    //这种方式的最坏情况就是原数据是逆序的, 那么其实还是O(n*n), 最好情况是原数据就是正序, 时间复杂度是O(N)
    //虽然二分查找减少了比较的次数, 但是原数据移位的次数还是得移, 所以对普通插入排序的改进有限
    template<class T> void insert_binary<T>::ibsort () {
    	for (int i = 0; i < data.size() - 1; i++) {
    		if (data[i + 1] < data[i]) {
    			//按从小到大原则, 找到原数据中不比curdata小的第一个数
    			int idx = find_insertindex(i, data[i + 1]);
    
    			//第0个数比第1个数小时直接交换, 其他照常顺序移位
    			if (i) {
    				T curdata = data[i + 1];
    				int j = i;
    				for (; j >= idx; j--) {
    					data[j + 1] = data[j];
    				}
    				data[idx] = curdata;
    			} else {
    				swap(0, 1);
    			}
    		}
    	}
    }
    
    template<class T> void insert_binary<T>::show (bool direct) {
    	if (direct) {
    		for (int i = 0; i < data.size(); i++) {
    			std::cout << data[i];
    			if (i != data.size() - 1) {
    				std::cout << ", ";
    			}
    		}
    	} else {
    		for (int i = data.size() - 1; i >= 0; i--) {
    			std::cout << data[i];
    			if (i != 0) {
    				std::cout << ", ";
    			}
    		}
    	}
    	std::cout << std::endl;
    }


    insert_binary.cpp(测试程序):

    #include "insert_binary_func.h"
    #include <stdlib.h>
    
    
    int main () {
    
    	int *testdata = new int[sizeof(int) * 30];
    	srand((int)time(0));
    	for (int i = 0; i < 30; i++) {
    		testdata[i] = rand() % 100;
    		std::cout << testdata[i] << " ";
    	}
    	std::cout << std::endl;
    
    	//int testdata[30] = {76, 64, 87, 30, 32, 47, 81, 12, 98, 34, 69, 92, 83, 45, 32, 50, 82, 56, 4, 78, 57, 13, 52, 8, 73, 55, 30, 27, 88, 33};
    	//int testdata[30] = {74, 1, 20, 8, 56, 65, 63, 39, 37, 47, 47, 53, 66, 62, 27, 10, 21, 94, 95, 1, 58, 56, 30, 95, 96, 17, 37, 3, 91, 96};
    	insert_binary<int> insert_binarysorter(testdata, 30);
    	insert_binarysorter.show(1);
    	delete []testdata;
    	return 0;
    }
    各方面时间复杂度和普通插入排序完全一样,虽然明显会快一些。


    3、链表插入排序:

    用链表的特性代替数组的特性,也就取消了移位这个过程。即相当于一个优先级链表创建过程。

    insert_slist.h(类声明):

    #include <vector>
    
    template<class T> struct node {
    	T data;
    	struct node *next;
    	node(T _data, struct node *_next):data(_data), next(_next){}
    };
    
    template<class T> class insert_slist {
    	node<T> *head;
    public:
    	insert_slist(T *data, int size);
    	insert_slist(std::vector<T> data);
    	~insert_slist();
    	void issort(T data);
    	void show(bool direct);
    };

    insert_slist_func.h(类实现):

    #include "insert_slist.h"
    #include <iostream>
    
    
    template<class T> insert_slist<T>::insert_slist (T *data, int size) {
    	head = 0;
    	for (int i = 0; i < size; i++) {
    		if (!head) {
    			head = new node<T>(data[i], 0);
    		} else {
    			issort(data[i]);
    		}
    	}
    }
    
    template<class T> insert_slist<T>::insert_slist (std::vector<T> data) {
    	head = 0;
    	for (int i = 0; i < data.size(); i++) {
    		if (!head) {
    			head = new node<T>(data[i], 0);
    		} else {
    			issort(data[i]);
    		}
    	}
    }
    
    template<class T> insert_slist<T>::~insert_slist () {
    	node<T> *cur = head;
    	while (cur) {
    		node<T> *next = cur->next;
    		delete cur;
    		cur = next;
    	}
    }
    
    //普通插入排序, 需要对索引i+1的违背排序方向数据, 顺序的从索引i-1向左依次进行比较和可能的原数据移位, 直到找到不比它大/小的数据时停止
    //折半插入排序, 在寻找应该在的位置的过程中做了改进, 利用左边数据的有序性, 通过二分查找寻找应该在的位置j, 再对[j, i+1]的数据进行原数据移位
    //折半插入排序减少了比较次数(由O(N)次比较减为O(logN)次比较, 但原数据移位依然为N次)
    //这里的链表插入排序, 和折半插入排序相反, 不减少比较的次数(依然为O(N)), 但利用链表的特性消灭了原数据移位(动态插入新的节点)
    //链表插入排序, 最坏情况下就是原数据是有序且逆序, 这样依然需要一次次的比较, 时间复杂度 = 1+2+3+...(n-1) = n*(n-1)/2->O(N*N). 最好情况就是原数据有序且正序, 时间复杂度就是O(N)
    //链表插入排序的平均时间复杂度被认为是O(N*N).
    //看到这里应该发现, 不论是折半插入排序, 还是链表插入排序, 确实都对普通插入排序的时间复杂度有所缓解, 但实质上都没有解决插入排序的问题, 并没有实际意义......对于插入排序还是去看希尔排序吧
    template<class T> void insert_slist<T>::issort (T curdata) {
    	node<T> *cur = head, *prev = head;
    	while (cur) {
    		if (cur->data > curdata) {
    			if (cur == head) {
    				node<T> *newhead = new node<T>(curdata, cur);
    				head = newhead;
    				return;
    			} else {
    				node<T> *newnode = new node<T>(curdata, cur);
    				prev->next = newnode;
    				return;
    			}
    		} else {
    			prev = cur;
    			cur = cur->next;
    		}
    	}
    
    	node<T> *newnode = new node<T>(curdata, 0);
    	prev->next = newnode;
    }
    
    template<class T> void insert_slist<T>::show (bool direct) {
    	if (direct) {
    		node<T> *cur = head;
    		while (cur) {
    			std::cout << cur->data;
    			if (cur->next) {
    				std::cout << ", ";
    			}
    			cur = cur->next;
    		}
    	} else {
    		std::vector<T> tmp;
    		node<T> *cur = head;
    		while (cur) {
    			tmp.push_back(cur->data);
    			cur = cur->next;
    		}
    		for (int i = tmp.size() - 1; i >= 0; i--) {
    			std::cout << tmp[i];
    			if (i != 0) {
    				std::cout << ", ";
    			}
    		}
    	}
    	std::cout << std::endl;
    }

    insert_slist.cpp(测试程序):

    #include "insert_slist_func.h"
    #include <stdlib.h>
    
    
    int main () {
    	int *testdata = new int[sizeof(int) * 30];
    	srand((int)time(0));
    	for (int i = 0; i < 30; i++) {
    		testdata[i] = rand() % 100;
    		std::cout << testdata[i] << " ";
    	}
    	std::cout << std::endl;
    	insert_slist<int> insert_slistsorter(testdata, 30);
    	insert_slistsorter.show(0);
    	delete []testdata;
    	return 0;
    }
    链表插入排序在完成了比较的过程,即找到应该插入的位置后,只需插入即可,完全不存在移位,这是因为链表而不是数组的原因。

    链表插入排序的时间复杂度同样完全被认为等同于普通插入排序,虽然明显会快一些。


    4、希尔排序:

    折半插入排序、链表插入排序都是在形式上设法提高些效率,但插入排序的根本的慢是因为,一旦原始数据是逆序的有序,那么势必就是涉及很多的比较/移位,所以它们并不是根本意义上的改进。

    希尔排序是真正意义上的插入排序的改进,希尔排序的排序方式依然是插入排序的方式,它的改进就是首先实现一小部分数据有序,然后再此基础上,再实现更多的一部分数据有序,这样一步步的逐渐实现更多的数据有序,最终实现全部的数据有序。在比较多的数据已经有序时,最终去做全部数据的插入排序时,时间复杂度就接近于O(N)了。

    希尔排序最好情况依然是O(N),最坏也依然是O(N * N),平均时间复杂度分析被认为是O(N^1.3)原因暂无搞清楚。


    insert_shell.h(类声明):

    #include <vector>
    
    template<class T> class insert_shell {
    	std::vector<T> data;
    	void swap(int i, int j);
    public:
    	insert_shell(T *_data, int size);
    	insert_shell(std::vector<T> _data);
    	~insert_shell(){data.clear();}
    	void ishellsort();
    	void show(bool direct);
    };

    insert_shell_func.h(类实现):

    #include "insert_shell.h"
    #include <iostream>
    
    
    template<class T> insert_shell<T>::insert_shell (T *_data, int size) {
    	for (int i = 0; i < size; i++) {
    		data.push_back(_data[i]);
    	}
    	ishellsort();
    }
    
    template<class T> insert_shell<T>::insert_shell (std::vector<T> _data) {
        for (int i = 0; i < _data.size(); i++) {
            data.push_back(_data[i]);
        }
        ishellsort();
    }
    
    template<class T> void insert_shell<T>::swap (int i, int j) {
    	if (i != j) {
    		T tmp = data[i];
    		data[i] = data[j];
    		data[j] = tmp;
    	}
    }
    
    //希尔排序: 依次达到一部分数据有序, 方式还是插入排序的方式只不过step从大逐渐到1, 最终达到全部数据有序
    //之所以希尔排序会比普通插入排序要快, 是因为插入排序适合于原数据有序时才会比较快, 省掉很多移位
    //所以先用一些步骤使数据先相对有序, 后面的排序逐渐越来越快, 到最后的step为1的普通插入排序时, 就会比较快了
    //希尔排序的复杂度分析, 最坏情况依然是O(N*N)即完全逆序时, 最好情况也依然是O(N)即完全正序时, 平均复杂度被认为是O(N^1.3)原因还未理解清楚
    //希尔排序的实际效果, 认为和以哪些step有关, 但具体情况还未弄清楚
    template<class T> void insert_shell<T>::ishellsort () {
    	int len = data.size();
    	int step = len/2;
    	while (step) {
    		//比如len=10, 先达到data[0]和data[5]有序, 然后依次达到data[0]和data[2]、data[0]和data[2]和data[4]、data[0]和data[2]和data[4]和data[8]有序
    		//最后依次达到整个有序
    		for (int i = step; i < data.size(); i += step) {
    			int j = i;
    			int curdata = data[j];
    			//这里其实还是插入排序, 只不过间距不是1而是step. 寻找按步长step, data[j]应该在的位置
    			while (j > 0) {
    				if (curdata < data[j - step]) {
    					data[j] = data[j - step];
    					j -= step;
    				} else {
    					break;
    				}
    			}
    			data[j] = curdata;
    		}
    
    		step = step/2;
    	}
    }
    
    template<class T> void insert_shell<T>::show (bool direct) {
    	if (direct) {
    		for (int i = 0; i < data.size(); i++) {
    			std::cout << data[i];
    			if (i != data.size() - 1) {
    				std::cout << ", ";
    			}
    		}
    	} else {
    		for (int i = data.size() - 1; i >= 0; i--) {
    			std::cout << data[i];
    			if (i != 0) {
    				std::cout << ", ";
    			}
    		}
    	}
    	std::cout << std::endl;
    }

    insert_shell.cpp(测试程序):

    #include "insert_shell_func.h"
    #include <stdlib.h>
    
    
    int main () {
    	int *testdata = new int[sizeof(int) * 12];
    	srand((int)time(0));
    	for (int i = 0; i < 12; i++) {
    		testdata[i] = rand() % 100;
    		std::cout << testdata[i] << ", ";
    	}
    	std::cout << std::endl;
    	insert_shell<int> insert_shellsorter(testdata, 12);
    	insert_shellsorter.show(1);
    	delete []testdata;
    	return 0;
    }


    展开全文
  • 链表插入排序 lintcode

    2016-10-18 10:10:08
    链表插入排序 难度系数 容易 通过率 31%  描述 笔记  数据  评测 用插入排序对链表排序 您在真实的面试中是否遇到过这个题?  Yes 样例 Given 1->3->2->0...

     链表插入排序

    难度系数 容易 通过率 31%

    用插入排序对链表排序

    样例

    Given 1->3->2->0->null, return 0->1->2->3->null

    package tju.cs.bigdata.chc;
    
    
    public class ListNode {
    	int val;
    	ListNode next;
    
    	ListNode(int val) {
    		this.val = val;
    		this.next = null;
    	}
    	
    	public ListNode createList(String s){
    		ListNode res = new ListNode(-1);
    		String[] strings = s.split("->");
    		ListNode cur = res;
    		for(String st : strings){
    			if(!st.equals("null"))cur.next = new ListNode(Integer.parseInt(st));
    			cur = cur.next;
    		}
    		
    		return res.next;
    	}
    	public void printList(ListNode l){
    		ListNode cur = l;
    		if(l == null)return;
    		while(cur != null){
    			System.out.print(cur.val + " ");
    			cur = cur.next;
    		}
    	}
    }

    package tju.cs.bigdata.chc;
    
    
    public class InsertionSortList {
    	   public ListNode insertionSortList(ListNode head) {
    	        // write your code here
    	        if(head == null || head.next == null){
    	            return head;
    	        }
    	        ListNode res = new ListNode(-1);
    	        ListNode cur = head;
    	        ListNode curtmp = res;
    	        while(cur != null){
    	            curtmp = res;
    	            
    	            while(curtmp.next != null && curtmp.next.val <= cur.val){
    	                curtmp = curtmp.next;
    	            }
    //	            curtmp.printList(curtmp);
    //	            cur.printList(cur);
    	            ListNode l = cur.next;
    	            cur.next = curtmp.next;
    	            curtmp.next = cur;
    	            cur = l;
    //	            if(cur != null)cur.printList(cur);
    //	            curtmp.printList(curtmp);
    	        }        
    	        return res.next;
    	        
    	    }
    	   public static void main(String[] args){
    		   String string = "1->3->2->0->null";
    		   ListNode res = new ListNode(-1).createList(string);
    		   res.printList(res);
    		   InsertionSortList insertionSortList = new InsertionSortList();
    		   ListNode res1 = insertionSortList.insertionSortList(res);
    		   res1.printList(res1);
    	   }
    }	
    


    展开全文
  • C语言链表插入排序

    千次阅读 2015-05-10 22:56:58
    C语言链表插入排序 大家好,我就是人见人爱 花见花开车见爆胎的小智 声音依旧是那么低沉切性感,现在又来给大家更新博客的第一视角了。 这期给大家介绍的是链表的插入排序。 具体代码如下: struct Student *...

    C语言链表插入排序

    大家好,我就是人见人爱 花见花开车见爆胎的小智 声音依旧是那么低沉切性感,现在又来给大家更新博客的第一视角了大笑

    这期给大家介绍的是链表的插入排序。

    具体代码如下:

    struct Student *Sort(struct student *h)

    {
    struct student *ptemp=h,*phead,*q,*r,*t;
    phead=(struct student *)malloc(sizeof(struct student )); //让phead指向头结点
    phead->next=NULL;
    while(ptemp!=NULL) //遍历要排序的链表ptemp
    {
    if(phead->next==NULL) //判断是否是第一个结点
    {
    phead->next=ptemp; //将ptemp链接到phead后面
    q=ptemp->next; //q指向ptemp的下一个结点
    ptemp->next=NULL; //ptemp的指针为空
    ptemp=q; //ptemp指向q
    }
    else
    {
    q=phead->next; //q指向phead的下一个结点
    r=phead; //r指向phead
    while(q!=NULL&&ptemp->aver<q->aver )
    {
    r=q;
    q=q->next;
    }
    t=ptemp->next; //t指向ptemp的下一个结点
    ptemp->next=r->next; //连接ptemp和r的下一个结点(q)
    r->next=ptemp; //连接r和ptemp
    ptemp=t; //ptemp指向t
    }
    }
    t=phead;
    phead=phead->next; //因为有头结点,所以要将phead向后移动一位
    free(t); //释放结点

    return phead;

    }

    鄙人认为:

    排序思想核心:创建新的头结点phead,使q指向phead的下一个结点,r指向phead,将待插入的结点(ptemp)一直插在r和q之间,不过用r和q的整体移动来控制ptemp的实际插入位置

    排序代码核心:

    q=phead->next;
    r=phead;

    while(q!=NULL&&ptemp->aver<q->aver )
    {
    r=q;
    q=q->next;
    }

    这段代码的意思是使结点r和q整体后移,找到ptemp实际要插入的位置,详细看下图:

    那么,随着这张图片的出现,本期的小智第一视角解说也就要结束了,欢迎大家多关注小智的博客,下期我们再见。大笑再见





    展开全文
  • LintCode 链表插入排序

    千次阅读 2017-03-27 22:28:14
    插入排序是十分常见的排序方式之一,类似于数组的插入排序,此题是关于链表插入排序。 原题给定一个以head为头节点的链表,下面再新建一个有序的dummy链表,通过把head链表 中的节点分别插入到dummy链表中完成对...
  • 链表插入排序 目录173. 链表插入排序鸣谢 173. 链表插入排序 用插入排序对链表排序 样例 1: 输入: 0->null 输出: 0->null 样例 2: 输入: 1->3->2->0->null 输出 :0->1->2->3->...
  • LintCode-链表插入排序

    2015-11-06 11:50:12
    容易 链表插入排序 用插入排序对链表排序 您在真实的面试中是否遇到过这个题?  Yes 样例 Given 1->3->2->0->null, return 0->1->2->3->null 冒泡法遍历 /** * ...
  • Insertion Sort List(链表插入排序)【难度:Medium】 Sort a linked list using insertion sort. 对一个链表使用插入排序。解题思路基于插入排序的思想,从链表头开始遍历,找到第一个大于当前节点的链表节点,...
  • 173链表插入排序

    2017-07-10 21:25:46
    题目描述:用插入排序链表排序样例 Given 1->3->2->0->null, return 0->1->2->3->null思路:插入排序的基本思想:将一个节点插入到一个有序的序列中。对于链表而言,要依次从待排序的链表中取出一个节点插入到...
  • 链表插入排序时,需要将一个链表拆分成两个链表,其中一个为有序链表,也就是只含头节点和一个数据节点,因为当只有一个数的时候就是有序的,另外一个链表含有剩下的数据节点,我们要实现的就是将这个含有剩下数据...
  • 3.链表插入排序, 4.希尔排序(又称缩小增量排序)。 插入排序属于稳定排序的一种(通俗地讲,就是两个相等的数不会交换位置) 。 1.直接插入排序! 思想:将一个记录插入到一个已经排好序的有序表中。 //示例代码...
  • 链表插入排序java实现

    2020-03-15 14:17:44
    插入排序的思想是:依次读取链表当前值,将其插入之前已排序好的部分中的正确位置,不断的向向已排序的新链表中添加新的节点,并且保证添加节点后的列表仍然有序,直至原链表遍历完毕。 /** * Definition for ...
  • LeetCode-147. Insertion Sort List (JAVA)链表插入排序
  • 链表插入排序 题目用插入排序对链表排序 样例Given 1->3->2->0->null, return 0->1->2->3->null 题解 /** * Definition for ListNode. * public class ListNode { * int val; * ListNode next; * ListNode(int...
  • 题目:链表插入排序 样例:Given 1->3->2->0->null,return 0->1->2->3->null。 思路:设置一个新链表,从原始链表中逐一进行判断插入到新链表中。 代码: class Solution { public: /** * @param ...
  • 173. 链表插入排序

    2018-06-10 11:44:19
    题目需求用插入排序链表排序样例Given 1-&gt;3-&gt;2-&gt;0-&gt;null, return 0-&gt;1-&gt;2-&gt;3-&gt;null解题思路/** * Definition of singly-linked-list: * class ...
  • 思路:定义一个临时链表存放已排序好的链表,将未排序好的节点依次插入链表元素:1,3,8,4,6,5,2 (递归到最后一个节点2) 第一轮:temp链表元素为2,head 为5,操作:将5插入到2后面 第二轮:temp链表元素为2...
  • Insertion Sort List 链表插入排序

    千次阅读 2014-08-31 22:33:55
    链表插入排序
  • 2、OJ147链表插入排序 虽然是插入排序的思想,但是做法和数组插入排序比较不同,核心思路是,将链表分为已排序和未排序两部分开的链表,已排序部分初始只有首元素一个节点,未排序的部分不断的按value大小,插入...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 142,124
精华内容 56,849
关键字:

链表插入排序