알고리즘, 구조 응용
각종 알고리즘 복잡 도:
정렬 법
평균 시간
최 악의 상황
안정 도
추가 공간
비고
거품 이 일다
O(n2)
O(n2)
안정시키다
O(1)
시간
교환 하 다.
O(n2)
O(n2)
불안정
O(1)
시간
선택 하 다.
O(n2)
O(n2)
불안정
O(1)
시간
끼어들다
O(n2)
O(n2)
안정시키다
O(1)
대부분 정렬 되 었 을 때 좋 습 니 다.
기수
O(logRB)
O(logRB)
안정시키다
O(n)
B 는 진수 (0 - 9), R 은 기수 (개 100)
Shell
O(nlogn)
O(ns) 1<2
불안정
O(1)
s 는 선택 한 그룹 입 니 다.
쾌속
O(nlogn)
O(n2)
불안정
O(nlogn)
옛날
병합 하 다
O(nlogn)
O(nlogn)
안정시키다
O(1)
옛날
쌓다
O(nlogn)
O(nlogn)
불안정
O(1)
옛날
1. 거품 정렬 (두 가지 비교)
public static void sort(int[] list)
{
int[] newList = new int[list.Length];
int copyValue = 0;
for (int i = 0; i < list.Length - 1;i++)
{
for (int j = i + 1; j < list.Length;j++)
{
if(list[i] < list[j])
{
copyValue = list[i];
list[i] = list[j];
list[j] = copyValue;
}
}
}
}2. 정렬 선택 (최대 색인, 교환 값 선택)
public static void sort(int[] list)
{
int maxIndex = 0;
for (int i = 0; i < list.Length - 1; i++)
{
maxIndex = i;
for (int j = i + 1; j < list.Length; j++)
{
if (list[j] > list[maxIndex])
{
maxIndex = j;
}
}
int maxValue = list[maxIndex];
list[maxIndex] = list[i];
list[i] = maxValue;
}
}3. 정렬 삽입 (후 앞으로, Check, 삽입)
public static void sort(int[] list)
{
for (int i = 1; i < list.Length; i++)
{
int originValue = list[i];
int j = i;
while ((j > 0) && (list[j - 1] > originValue))
{
list[j] = list[j - 1];
--j;
}
list[j] = originValue;
}
}4. 힐 정렬
public static 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 originValue = list[i - 1];
int j = i;
while ((j > inc) && (list[j - inc - 1] > originValue))
{
list[j - 1] = list[j - inc - 1];
j -= inc;
}
list[j - 1] = originValue;
}
}
}5. 빠르다
///
/// </summary>
/// <param name="list"></param>
/// <param name="low"></param>
/// <param name="high"></param>
public static void Sort(int[] list, int low, int high)
{
int pivot;
int l, r;
int mid;
if (high <= low)
return;
else if (high == low + 1)
{
if (list[low] > list[high])
Swap(ref list[low], ref list[high]);
return;
}
mid = (low + high) >> 1;
pivot = list[mid];
Swap(ref list[low], ref list[mid]);
l = low + 1;
r = high;
do
{
while (l <= r && list[l] < pivot)
l++;
while (list[r] >= pivot)
r--;
if (l < r)
Swap(ref list[l], ref list[r]);
} while (l < r);
list[low] = list[r];
list[r] = pivot;
if (low + 1 < r)
Sort(list, low, r - 1);
if (r + 1 < high)
Sort(list, r + 1, high);
}
6. 귀속
2. 데이터 구조: 1. 뉴스 맥 스 의 앞 순서, 중간 순서, 뒤 순서 가 반복 되 는 실현
-- --#region -- --
/**//**//**//// ,
/// ： ， ( )
public class TreeNode
{
private TreeNode leftNode;
private TreeNode rightNode;
private int data;
public TreeNode(int nodeData)
{
data = nodeData;
leftNode = rightNode = null;//
}
public TreeNode LeftNode
{
get
{
return leftNode;
}
set
{
leftNode = value;
}
}
public TreeNode RightNode
{
get
{
return rightNode;
}
set
{
rightNode = value;
}
}
public int Data
{
get
{
return data;
}
set
{
data = value;
}
}
public void Insert(int insertValue)//
{
if (insertValue < data)
{
if (leftNode == null)
leftNode = new TreeNode(insertValue);
else
leftNode.Insert(insertValue);
}
else if (insertValue > data)
{
if (rightNode == null)
rightNode = new TreeNode(insertValue);
else
rightNode.Insert(insertValue);
}
}
}
public class Tree
{
private TreeNode root;
public Tree()
{
root = null;
}
//
public void InsertNode(int insertValue)
{
lock (this)
{
if (root == null)
root = new TreeNode(insertValue);
else
root.Insert(insertValue);
}
}
//
public void PreorderTraversal()
{
lock (this)
{
PreorderHelper(root);
}
}
private void PreorderHelper(TreeNode node)//
{
if (node == null)
return;
Console.Write(node.Data + " ");
PreorderHelper(node.LeftNode);
PreorderHelper(node.RightNode);
}
//
public void InorderTraversal()
{
lock (this)
{
InorderHelper(root);
}
}
public void InorderHelper(TreeNode node)
{
if (node == null)
return;
InorderHelper(node.LeftNode);
Console.Write(node.Data + " ");
InorderHelper(node.RightNode);
}
//
public void PostorderTraversal()
{
lock (this)
{
PostorderHelper(root);
}
}
public void PostorderHelper(TreeNode node)
{
if (node == null)
return;
PostorderHelper(node.LeftNode);
PostorderHelper(node.RightNode);
Console.Write(node.Data + " ");
}
}
#endregion2. 가난 한 녀석 - 링크 처리
-- --#region -- --
namespace List
{
/**//**//**//// <summary>
/// Summary description for ListNode.
/// </summary>
//
public class ListNode
{
public ListNode(int NewValue)
{
Value = NewValue;
}
/**//**//**//// <summary>
///
/// </summary>
public ListNode Previous;
/**//**//**//// <summary>
///
/// </summary>
public ListNode Next;
/**//**//**//// <summary>
///
/// </summary>
public int Value;
}
/**//**//**//// <summary>
///
/// . LIST , ，Head ,Tail, Current， ，
/// Append ，MoveFrist,MovePrevious，MoveNext,MoveLast ,Delete,InsertAscending,InsertUnAscending ,Clear
/// ， ， , ， ， ，GetCurrentValue（） 。
/// </summary>
public class Clist
{
public Clist()
{
//
//
ListCountValue = 0;
Head = null;
Tail = null;
}
/**//**//**//// <summary>
///
/// </summary>
private ListNode Head;
/**//**//**//// <summary>
///
/// </summary>
private ListNode Tail;
/**//**//**//// <summary>
///
/// </summary>
private ListNode Current;
/**//**//**//// <summary>
///
/// </summary>
private int ListCountValue;
/**//**//**//// <summary>
///
/// </summary>
public void Append(int DataValue)
{
ListNode NewNode = new ListNode(DataValue);
if (IsNull())
//
{
Head = NewNode;
Tail = NewNode;
}
else
{
Tail.Next = NewNode;
NewNode.Previous = Tail;
Tail = NewNode;
}
Current = NewNode;
//
ListCountValue += 1;
}
/**//**//**//// <summary>
///
/// </summary>
public void Delete()
{
//
if (!IsNull())
{
//
if (IsBof())
{
Head = Current.Next;
Current = Head;
ListCountValue -= 1;
return;
}
//
if (IsEof())
{
Tail = Current.Previous;
Current = Tail;
ListCountValue -= 1;
return;
}
//
Current.Previous.Next = Current.Next;
Current = Current.Previous;
ListCountValue -= 1;
return;
}
}
/**//**//**//// <summary>
///
/// </summary>
public void MoveNext()
{
if (!IsEof()) Current = Current.Next;
}
/**//**//**//// <summary>
///
/// </summary>
public void MovePrevious()
{
if (!IsBof()) Current = Current.Previous;
}
/**//**//**//// <summary>
///
/// </summary>
public void MoveFrist()
{
Current = Head;
}
/**//**//**//// <summary>
///
/// </summary>
public void MoveLast()
{
Current = Tail;
}
/**//**//**//// <summary>
///
/// </summary>
public bool IsNull()
{
if (ListCountValue == 0)
return true;
return false;
}
/**//**//**//// <summary>
///
/// </summary>
public bool IsEof()
{
if (Current == Tail)
return true;
return false;
}
/**//**//**//// <summary>
///
/// </summary>
public bool IsBof()
{
if (Current == Head)
return true;
return false;
}
public int GetCurrentValue()
{
return Current.Value;
}
/**//**//**//// <summary>
///
/// </summary>
public int ListCount
{
get
{
return ListCountValue;
}
}
/**//**//**//// <summary>
///
/// </summary>
public void Clear()
{
MoveFrist();
while (!IsNull())
{
// ,
Delete();
}
}
/**//**//**//// <summary>
///
/// </summary>
public void Insert(int DataValue)
{
ListNode NewNode = new ListNode(DataValue);
if (IsNull())
{
// ，
Append(DataValue);
return;
}
if (IsBof())
{
//
NewNode.Next = Head;
Head.Previous = NewNode;
Head = NewNode;
Current = Head;
ListCountValue += 1;
return;
}
//
NewNode.Next = Current;
NewNode.Previous = Current.Previous;
Current.Previous.Next = NewNode;
Current.Previous = NewNode;
Current = NewNode;
ListCountValue += 1;
}
/**//**//**//// <summary>
///
/// </summary>
public void InsertAscending(int InsertValue)
{
// ：InsertValue
//
if (IsNull())
{
//
Append(InsertValue);
return;
}
//
MoveFrist();
if ((InsertValue < GetCurrentValue()))
{
// ， ，
Insert(InsertValue);
return;
}
while (true)
{
if (InsertValue < GetCurrentValue())
{
// ， ，
Insert(InsertValue);
break;
}
if (IsEof())
{
//
Append(InsertValue);
break;
}
//
MoveNext();
}
}
/**//**//**//// <summary>
///
/// </summary>
public void InsertUnAscending(int InsertValue)
{
// ：InsertValue
//
if (IsNull())
{
//
Append(InsertValue);
return;
}
//
MoveFrist();
if (InsertValue > GetCurrentValue())
{
// ， ，
Insert(InsertValue);
return;
}
while (true)
{
if (InsertValue > GetCurrentValue())
{
// ， ，
Insert(InsertValue);
break;
}
if (IsEof())
{
//
Append(InsertValue);
break;
}
//
MoveNext();
}
}
}
}
#endregion3. 스 택 작업 실현
namespace StackNameSpace
{
/**//// <summary>
/// Class1 。
/// </summary>
public class Stack
{
-- --#region -- --
private int count = 0;
private Node first = null;//
public bool Empty
{
get
{
return (first == null);
}
}
public int Count
{
get
{
return count;
}
}
public object Pop()//
{
if (first == null)
{
throw new InvalidOperationException("Can not pop from an empty stack;");
}
else
{
object temp = first.Value;
first = first.Next;
count--;
return temp;
}
}
public void push(object o)//
{
first = new Node(o, first);
count++;
}
public Stack()
{
//
// TODO:
//
}
#endregion
}
class Node
{
-- --#region -- --
public Node Next;
public object Value;
public Node(object value) : this(value, null) { }
public Node(object value, Node next)
{
Next = next;
Value = value;
}
#endregion
}
}3. 기타 알고리즘
1、
-- ( ) --#region -- ( ) --
public static void heapSort(int[] input)
{
int root_count = input.Length / 2;
for (int i = root_count - 1; i >= 0; i--)
{
int left = 0;
int right = 0;
if (2 * i + 1 < input.Length) left = input[2 * i + 1];
if ((2 * i + 2) < input.Length) right = input[2 * i + 2];
if (left >= right && left > input[i])
{
Sort.swap(ref input[i], ref input[2 * i + 1]);
Sort.nodeSort(input, 2 * i + 1, input.Length - 1);
}
else if (right >= left && right > input[i])
{
Sort.swap(ref input[i], ref input[2 * i + 2]);
Sort.nodeSort(input, 2 * i + 2, input.Length - 1);
}
}
for (int j = input.Length - 1; j > 0; j--)
{
Sort.swap(ref input[0], ref input[j]);
Sort.nodeSort(input, 0, j - 1);
}
}
public static void nodeSort(int[] input, int index,int end)
{
//
while ((2 * index + 1) <= end)
{
//
if ((2 * index + 2) <= end)
{
//
if (input[2 * index + 1] >= input[2 * index + 2] && input[2 * index + 1] > input[index])
{
Sort.swap(ref input[index], ref input[index * 2 + 1]);
index = 2 * index + 1;
}
//
else if (input[2 * index + 2] >= input[2 * index + 1] && input[2 * index + 2] > input[index])
{
Sort.swap(ref input[index], ref input[index * 2 + 2]);
index = 2 * index + 2;
}
//
else
{
return;
}
}
else
//
{
//
if (input[2 * index + 1] > input[index])
{
Sort.swap(ref input[index], ref input[index * 2 + 1]);
index = 2 * index + 1;
}
else
{
//
return;
}
}
}
}
#endregion이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
