没有合适的资源?快使用搜索试试~ 我知道了~
基本排序算法 字符串的操作(包括判断最长回文、求子串等) 链表的操作(链表的有序插入,删除、递归删除等) 双向链表的操作(插入和删除)
资源详情
资源评论
资源推荐
排序总结
1 冒泡排序:
public static void booble(int[] arr) //冒泡排序
{
int temp;
for(int i=0;i<arr.Length-1;i++)
for(int j=0;j<arr.Length-i-1;j++)
{
if(arr[j]>arr[j+1])
{
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
foreach(int i in arr)
Console.WriteLine(i );
Console.ReadLine();
}
2 选择排序
public static void SelectSort(int []arr) //选择排序
{
int temp;
int min;
for(int i=0;i<arr.Length;i++)
{
min = i;
for(int j=i+1;j<arr.Length;j++)
{
if (arr[j] > arr[min])
min = j;
if(min!=i)
{
temp=arr[min];
arr[min]=arr[i];
arr[i] = temp;
}
}
}
foreach(int i in arr)
{
Console.WriteLine(i);
}
Console.ReadLine();
}
3 插入排序
public static void InsertSort(int [] arr) // 插入排序
{
int inner, temp;
for(int i=1;i<arr.Length;i++)
{
temp = arr[i];
inner = i;
while(inner>0&&arr[inner-1]>=temp)
{
arr[inner] = arr[inner - 1];
inner -= 1;
}
arr[inner] = 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=list[low];
while(low<high)
{
while(low<high && list[high]>=pivot)
high--;
if(low!=high)
{
temp = list[low];
list[low]=list[high];
list[high] = temp;
low++;
}
while(low<high && list[low]<=pivot)
low++;
if(low!=high)
{
temp = list[low];
list[low]=list[high];
list[high] = 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 <= low)
return;
else if (high == low + 1)
{
if (list[low] > list[high])
{
temp = list[low];
list[low] = list[high];
list[high] = 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 <= list.Length / 9; inc = 3 * inc + 1) ;
for (; inc > 0; inc /= 3)
{
for (int i = inc + 1; i <= list.Length; i += inc)
{
int t = list[i - 1];
int j = i;
while ((j > inc) && (list[j - inc - 1] > t))
{
list[j - 1] = list[j - inc - 1];
j -= inc;
}
list[j - 1] = t;
}
}
}
}
6 堆排序(Heap Sort)
堆排序只需要一个记录大小的辅助空间,每个待排序的记录仅占有一个存储空间。
堆的定义如下:n 个元素的序列{k1, k2, … , kn} 当且仅当满足下关系时,称之为堆。
{k1≤k2i; ki≤k2i+1} 或 {ki≥k2i; ki≥k2i+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; }
}
剩余59页未读,继续阅读
jimson_ma
- 粉丝: 25
- 资源: 13
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功
评论0