基本算法+C#++(排序,字符串,链表).doc

排序总结1 冒泡排序： public static void booble(int arr) /冒泡排序 int temp; for(int i=0;iarr.Length-1;i+) for(int j=0;jarrj+1) temp = arrj; arrj = arrj + 1; arrj + 1 = temp; foreach(int i in arr) Console.WriteLine(i ); Console.ReadLine(); 2 选择排序(一种简单直观的排序算法。它的工作原理如下。首先在未排序序列中找到最小元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小元素，然后放到排序序列最前。以此类推，直到所有元素均排序完毕) public static void SelectSort(int arr) /选择排序 int temp; int mindx; for(int i=0;iarr.Length;i+) mindx = i; for(int j=i+1;j arrmindx) mindx = j; if(mindx!=i) temp=arrmindx;arrmindx=arri;arri = temp; foreach(int i in arr) Console.WriteLine(i); Console.ReadLine(); 3 插入排序(将一个记录插入到已排好序的有序列中，从而得到一个新的，记录数增1的有序序列。待插记录依次比较已经排好序列，如果序列数大于该待插记录，那么该序列往后挪一位，直到找到序列小于待插记录，那么此时插入到该序列的后一个位置，依次上面操作，直至插完位置。)public static void InsertSort(int arr) / 插入排序 int inner, temp; for(int i=1;i0 & arrinner-1=temp) arrinner = arrinner - 1; inner -= 1; arrinner = temp; foreach(int i in arr) Console.WriteLine(i); Console.ReadLine(); 4 快速排序 public static int Partition(int list, int low, int high) int temp; int pivot; pivot=listlow; while(lowhigh) while(low=pivot) high-; if(low!=high) temp = listlow; listlow=listhigh; listhigh = temp; low+; while(lowhigh & listlow=pivot) low+; if(low!=high) temp = listlow; listlow=listhigh; listhigh = temp; high-; return low; public static void QuickSort(int list, int low, int high) /int newlow = low; /int newhigh = high; int temp = 0; if (high listhigh) temp = listlow; listlow = listhigh; listhigh = temp; return; else int pivot=Partition(list,low,high); QuickSort(list,low,pivot-1); QuickSort(list,pivot+1,high); 5 希而排序 思想：希尔排序是将组分段,进行插入排序程序如下： public class ShellSorter / public void Sort(int list) int inc; for (inc = 1; inc 0; inc /= 3) for (int i = inc + 1; i inc) & (listj - inc - 1 t) listj - 1 = listj - inc - 1; j -= inc; listj - 1 = t; 6 堆排序（Heap Sort）堆排序只需要一个记录大小的辅助空间，每个待排序的记录仅占有一个存储空间。堆的定义如下：n个元素的序列k1, k2, , kn 当且仅当满足下关系时，称之为堆。k1k2i; kik2i+1 或 kik2i; kik2i+1，(i=1, 2, , n/2)若将和此序列对应的一堆数组（即以一堆数组作此序列的存储结构）看成是一个完全二叉树，则堆的含义表明，完全二叉树中所有非终端结点的值均不大于（或小于）其左、右孩子结点的值。由此，若序列k1, k2, , kn 是堆，则堆顶元素（或完全二叉树的根）必为序列中n个元素的最小值（或最大值）。例如，下列两个序列为堆，对应的完全二叉树如图。若在输出堆顶的最小值之后，使得剩余n-1个元素的序列重又建成一个堆，则得到n个元素中的次小值，如此反复执行，便能得到一个有序序列，这个过程称之为堆排序。由此，实现堆排序需要解决两个问题：（1）如何由一个无序序列建成一个堆？（2）如何在输出堆顶元素之后，调整剩余元素成为一个新的堆？下面将从实际数据中演示其排序中的各个操作。原始数组： 22 53 72 11 34 44 11 15 28 3 10 65全程交换完成，得到最小值为3并且输出它。从序列中删除3，重新建立堆。以次循环，直到全部输出完成为止。我们称这个自堆顶至叶子的调整过程为“筛选”。7 归并排序合并排序（Merge Sort）又称归并排序，是又一类不同的排序方法，合并的含义就是将两个或两个以上的有序数据序列合并成一个新的有序数据序列，因此它又叫归并算法。它的基本思想就是假设数组A有N个元素，那么可以看成数组A是又N个有序的子序列组成，每个子序列的长度为1，然后再两两合并，得到了一个 N/2 个长度为2或1的有序子序列，再两两合并，如此重复，值得得到一个长度为N的有序数据序列为止，这种排序方法称为2路合并排序。 例如数组采用归并排序算法的操作过程如下图所示：原始数组： 22 53 72 11 34 44 11 15 28 3 10 65第一次合并： 22 53 11 72 34 44 11 15 3 28 10 65 第二次合并： 11 22 53 72 11 15 34 44 3 10 28 65第四次合并： 11 11 15 22 34 44 53 72 3 10 28 65第五次合并： 3 10 11 11 15 22 28 34 44 53 65 72排序结果： 3 10 11 11 15 22 28 34 44 53 65 72合并算法的核心操作就是将一维数组中前后相邻的两个两个有序序列合并成一个有序序列。合并算法也可以采用递归算法来实现，形式上较为简单,但实用性很差。合并算法的合并次数是一个非常重要的量,根据计算当数组中有3到4个元素时,合并次数是2次,当有5到8个元素时,合并次数是3次,当有9到16个元素时,合并次数是4次，按照这一规律,当有N个子序列时可以推断出合并的次数是X(2=N,符合此条件的最小那个X)。 其时间复杂度为：O(nlogn).所需辅助存储空间为：O(n)1,两个有序单向链表合并成一个有序链表class Node private int data; private Node next; public int Data set this.data = value; get return data; public Node Next get return next; set this.next = value; public Node(int d) this.data = d; this.next = null; public Node() this.data = 0; this.next = null; class LinkList private Node head; public LinkList() this.head = null; public Node Head get return head; set this.head = value; /print the element of the linklistnodes public void Display() Node cur = new Node(); cur = head; Console.WriteLine(nthe elements of the LinkList are:); Console.WriteLine(); while (cur != null) Console.Write( 0 , cur.Data); cur = cur.Next; /insert a new node public void Insert(int data) Node node = new Node(data); if (head = null) head = node; return; else Node cur = new Node(); cur = head; Node prev = null; while (cur != null) if (data = cur.Data) if (prev = null) head = node; node.Next = cur; else prev = new Node(); prev.Data = data; prev.Next = node; node.Next = cur; return; else prev = cur; cur = cur.Next; prev.Next = node; /merge two linklist together. public static Node Merge(Node head, Node list2) Node p, p1, p2; /p1 = p.Next; p = head ; p1 = p.Next ; p2 = list2; while (p1 != null & p2 != null) if (p1.Data j.Link.Element) int temp = j.Element; j.Element = j.Link.Element; j.Link.Element = temp; /选择sorting 小-大 public void SortInsert(Node header) Node min = new Node (); for (Node i = header.Link; i.Link != null; i = i.Link) /min = i.Element; min =i; for (Node j = i.Link; j != null; j = j.Link) if (j.Element min.Element ) min = j; int t = min.Element; min.Element = i.Element; i.Element = t; public void AddTen() Node current=new Node (); current =header ; for (int i = 1; inext-next;q每次移动一个位置,即q=q-next; 当p到达最后一个结点时,q就是中间结点了 public int SearchMid() Node p = new Node(); p = header.Link; Node q = new Node(); q = header.Link; if (p = null) Console.WriteLine(is empty!); return -1; else while (true) p = p.Link.Link; q = q.Link; if (p = null) break; else if (p.Link = null) break; /else continue; return q.Element; / 2 delete a node without any others node help public void DeleteWithout(Node current, int item) if (current = null) Console.WriteLine(is empty); if (current.Element = item) /current = current.Link; newHeader = newHeader.Link; else if (current.Link.Element != item) DeleteWithout(current.Link, item); else current.Link = current.Link.Link; /return current; public void newInsert(int item) Node current = new Node(); Node newNode = new Node(item); current = header; while (current.Link != null) current = current.Link; current.Link = newNode; newNode.Link = null; public void AddNode(int item) Node newNode = new Node(item); Node current = new Node(); if (newHeader = null) newHeader = newNode; else current = newHeader; while (current.Link != null) current = current.Link; current.Link = newNode; public Node Find(int item) / if not found ,then insert to the last position. Node current = new Node(); current = header; while (current.Element != item & current.Link != null) current = current.Link; return current; public void Delete(int item) Node current = new Node(); current = header; while (current.Link != null & current.Link.Element != item) current = current.Link; if (current.Link = null) Console.WriteLine(not found); else current.Link = current.Link.Link; public void Print() Node current = new Node(); current = header; while (current.Link != null) Console.Write(current.Link.Element + ); current = current.Link; public void newPrint() Node current = new Node(); current = header; while (current.Link != null) Console.Write(current.Link.Element + -); current = current.Link; public void newPrintH() Node current = new Node(); current = newHeader; while (current != null) Console.Write(current.Element + -); current = current.Link; public void Reverse() /has header with a 0 value ,not a recursion(非递归反转) Node current = new Node(); current = header.Link; /important,else create cycle /Console.WriteLine(the header is:n); Console.WriteLine(header.Element);/ Node next = null; Node previous = null; while (current != null) next = current.Link; current.Link = previous; previous = current; current = next; header.Link = previous; /current = header.Link; / header.Link = next; Node next = null; public Node ReverseH(Node header, Node previous) / ia recursion reverse (递归反转) next = header