《基本算法+c#++(排序,字符串,链表)》由会员分享，可在线阅读，更多相关《基本算法+c#++(排序,字符串,链表)（39页珍藏版）》请在金锄头文库上搜索。
1、 1 / 39排序总结1 冒泡排序：public static void booble(int arr) /冒泡排序int temp;for(int i=0;iarrj+1)temp = arrj;arrj = arrj + 1;arrj + 1 = temp;foreach(int i in arr)Console.WriteLine(i );Console.ReadLine();2 选择排序(一种简单直观的排序算法。它的工作原理如下。首先在未排序序列中找到最小元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小元素，然后放到排序序列最前。以此类推，直到所有元素均排序完毕)
2、public static void SelectSort(int arr) /选择排序int temp;int mindx;for(int i=0;i arrmindx)mindx = j;if(mindx!=i)temp=arrmindx;arrmindx=arri;arri = temp;foreach(int i in arr) 2 / 39Console.WriteLine(i);Console.ReadLine();3 插入排序(将一个记录插入到已排好序的有序列中，从而得到一个新的，记录数增 1 的有序序列。待插记录依次比较已经排好序列，如果序列数大于该待插记录，那么该序列往后挪一
3、位，直到找到序列小于待插记录，那么此时插入到该序列的后一个位置，依次上面操作，直至插完位置。)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
4、 low, int high) int temp; int pivot; pivot=listlow; while(low=pivot) high-; if(low!=high) temp = listlow; 3 / 39listlow=listhigh;listhigh = temp;low+; while(low listhigh)temp = listlow;listlow = listhigh;listhigh = temp;return;elseint pivot=Partition(list,low,high); QuickSort(list,low,pivot-1); Quic
5、kSort(list,pivot+1,high);5 希而排序 4 / 39思想：希尔排序是将组分段,进行插入排序程序如下：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）堆排序只需要一个记录大小的辅助空间，每个待排序的记录仅占有一个
6、存储空间。堆的定义如下：n 个元素的序列k1, k2, , kn 当且仅当满足下关系时，称之为堆。k1k2i; kik2i+1 或 kik2i; kik2i+1，(i=1, 2, , n/2)若将和此序列对应的一堆数组（即以一堆数组作此序列的存储结构）看成是一个完全二叉树，则堆的含义表明，完全二叉树中所有非终端结点的值均不大于（或小于）其左、右孩子结点的值。由此，若序列k1, k2, , kn 是堆，则堆顶元素（或完全二叉树的根）必为序列中 n 个元素的最小值（或最大值）。例如，下列两个序列为堆，对应的完全二叉树如图。若在输出堆顶的最小值之后，使得剩余 n-1 个元素的序列重又建成一个堆，则得
7、到 n个元素中的次小值，如此反复执行，便能得到一个有序序列，这个过程称之为堆排序。 5 / 39由此，实现堆排序需要解决两个问题：（1）如何由一个无序序列建成一个堆？（ 2）如何在输出堆顶元素之后，调整剩余元素成为一个新的堆？下面将从实际数据中演示其排序中的各个操作。原始数组： 22 53 72 11 34 44 11 15 28 3 10 65全程交换完成，得到最小值为 3 并且输出它。从序列中删除 3，重新建立堆。以次循环，直到全部输出完成为止。我们称这个自堆顶至叶子的调整过程为“筛选”。7 归并排序合并排序（Merge Sort）又称归并排序，是又一类不同的排序方法，合并的含义就是将两个
8、或两个以上的有序数据序列合并成一个新的有序数据序列，因此它又叫归并算法。它的基本思想就是假设数组 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
9、 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 次,当有
10、 9 到 16 个元素时, 合并次数是 4 次，按照这一规律,当有 N 个子序列时可以推断出合并的次数是 X(2=N,符合此条件的最小那个 X)。 其时间复杂度为：O(nlogn). 所需辅助存储空间为：O(n)1,两个有序单向链表合并成一个有序链表class Nodeprivate int data;private Node next;public int Dataset this.data = value; 6 / 39get return data; public Node Nextget return next; set this.next = value; public Node(i
11、nt d)this.data = d;this.next = null;public Node()this.data = 0;this.next = null;class LinkListprivate Node head;public LinkList()this.head = null;public Node Headget return head; set this.head = value; /print the element of the linklistnodespublic void Display()Node cur = new Node();cur = head;Conso
12、le.WriteLine(nthe elements of the LinkList are:);Console.WriteLine();while (cur != null)Console.Write( 0 , cur.Data);cur = cur.Next;/insert a new node 7 / 39public void Insert(int data)Node node = new Node(data);if (head = null)head = node;return;elseNode cur = new Node();cur = head;Node prev = null
13、;while (cur != null)if (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 =
14、j.Link)if (j.Element next-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;elsewhile (true)p = p.Link.Link;q = q.Link; 12 / 39if (p = null) break;else if (p.Link = null) break;/else continue;return q.Element;/ 2 delete a node without any others node helppublic void DeleteWithout(Node current, int item)if (current = null)Console.WriteLine(is empty);if (current.Element = item)/current = current.Link;newHeader = newHeader.Link;elsei
