일반적인 정렬 알고리즘

정렬 은 컴퓨터 에서 자주 진행 되 는 작업 으로 그 목적 은 '무질서' 의 기록 순 서 를 '질서 있 는' 기록 순서 로 조정 하 는 것 이다.   
    흔히 볼 수 있 는 정렬 알고리즘: 거품, 빠 른 배열, 삽입, 힐, 선택, 쌓 기, 병합.
1. 거품 정렬
원리: 무질서 한 배열 로 오름차 순 으로 배열 된다.int i 는 순환 횟수 를 대표 하고 int j 는 배열 의 아래 표 시 를 대표 하 며 if (arr [j] > arr [j + 1]) 는 위 치 를 교환 하고 순서대로 유추 합 니 다.매번 한 번 순환 할 때마다 하나의 숫자 는 그 에 상응하는 위치 에 있다.
원본 코드:

void Bubble_sort(int arr[],int len)
{
	int i;
	for(i=0;iarr[j+1])
			{
				int tmp=arr[j];
				arr[j]=arr[j+1];
				arr[j+1]=tmp;
			}
		}
	}
}

시간 복잡 도 o (n ^ 2), 공간 복잡 도 o (1).
2. 빠 른 줄:
원리: 중간 에서 양쪽 으로 탐색 하고 서열 에서 정확 한 기 수 를 선택 하여 참고 하 는 수 를 만 들 고 왼쪽 의 첫 번 째 수 를 예 로 들 어 서열 중의 모든 기준 기수 보다 큰 수 를 그의 오른쪽 에 놓 고 작은 것 을 그의 왼쪽 에 놓 으 며 최종 적 으로 기준 기수 의 위 치 를 확인한다.
두 변수 left, right 를 정의 하면 포인터 로 볼 수 있 습 니 다. 해당 하 는 요 소 를 지정 할 수 있 습 니 다. 하 나 는 가장 왼쪽 을 가리 키 고 하 나 는 가장 오른쪽 을 가리 키 며 left 를 준 기수 로 선택 합 니 다. 가장 왼쪽 의 수 와 비교 할 수 있 습 니 다. 준 기수 가 right 가 가리 키 는 수 보다 적 을 때 right -, 예 를 들 어 right 가 가리 키 는 수 보다 크 면 arr [left] = arr [right], 준 기수 가 왼쪽 의 값 보다 클 때 left +,왼쪽 값 보다 작 으 면 arr [right] = arr [left] 는 마지막 으로 정확 한 위치 에 준 기 수 를 두 고 상기 절 차 를 반복 합 니 다.
원본 코드:

void Quick_sort(int arr[],int Front,int Back)
{
	int left=Front;
	int right=Back;
	if (left  arr[left])
			{
				left++;
			}
			arr[right] = arr[left];
		}
		arr[left] = tmp;
		Quick_sort(arr,Front,left-1);
		Quick_sort(arr,left+1,Back);
	}
}

시간 복잡 도 o (nlog2n), 공간 복잡 도 o (nlog2n)
3. 정렬 삽입:
원리: 정렬 을 삽입 하 는 것 은 원래 차지 해 야 할 위치 에 숫자 를 삽입 하 는 것 을 말한다.
원본 코드:

void Insertsort(int arr[],int len)
{
	int i = 0;
	for (i = 0; i =0 && arr[pos] > tmp)
		{
			arr[pos+1] = arr[pos];
			pos--;
		}
		arr[pos+1] = tmp;
	}
}

시간 복잡 도 o (n ^ 2), 공간 복잡 도 o (1).
4. 힐 정렬
원리: 힐 정렬 은 정렬 을 삽입 하 는 개선 을 바탕 으로 전체 대기 요 소 를 여러 개의 키 서열 (특정한 증분 요소 로 구성 되 어 있 음) 로 나 누 어 각각 정렬 을 한 다음 에 증 가 를 줄 이 고 정렬 을 하 는 것 이다. 이 전체 요소 가 기본적으로 질서 가 있 을 때 (증 가 량 이 충분 하 다) 전체 요 소 를 한 번 삽입 하여 정렬 하 는 것 이다.
원본 코드:

void ShellSort(int arr[], int len)
{
	int gap = len;
	while (gap)
	{
		gap = gap/2;
		for (int i = gap; i =0 && arr[pos] > tmp)
			{
				arr[pos+gap] = arr[pos];
				pos-=gap;
			}
			arr[pos+gap] = tmp;
		}
	}
}

시간 복잡 도 o (n ^ 2), 공간 복잡 도 o (1).
5. 정렬 선택
원리: 대기 서열 에서 첫 번 째 요 소 를 최소 로 기록 하고 첫 번 째 위 치 는 최소 위치 로 기록 하 며 나머지 모든 요소 에서 최소 와 의 교환 을 찾 습 니 다.
원본 코드:

void SelectSort(int arr[], int len)
{
	for (int i = 0; i  
  
     o(n^2),     o(1).
 
  
6、  
 
  
          ，         ，                ，             ，          ，           ，        。
 
  
  ：
 
  
void HeapDown(int arr[],int i,int len)
{
	int parent=i;
	int child=2*i+1;
	while (child arr[parent])
		{
			swap(arr[parent],arr[child]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}
void CreateHeap(int arr[],int len)
{
	int i=0;
	for(i=len/2-1;i>=0;i--)
	{
		HeapDown(arr,i,len);
	}
}

void HeapSort(int arr[],int len)
{
	CreateHeap(arr,len);
	for (int i = len-1; i >= 0; i--)
	{
		swap(arr[0],arr[i]);
		HeapDown(arr,0,i);
	}
}
  
시간 복잡 도 o (nlog2n), 공간 복잡 도 o (1).
7. 병합 정렬
원본 코드:
void MergeArray(int arr[], int low, int mid, int high,int a[])
{
	int i = low;
	int j = mid+1;
	int k = 0;
	while (i <= mid && j <= high)
	{
		if (arr[i] <= arr[j])
		{
			a[k] = arr[i];
			i++;
			k++;
		}
		else
		{
			a[k] = arr[j];
			j++;
			k++;
		}
	}
	while (i<=mid)
	{
		a[k] = arr[i];
		i++;
		k++;
	}
	while (j <= high)
	{
		a[k] = arr[j];
		j++;
		k++;
	}
	for (i = 0; i  
  
     o(nlog2n),     o(n)。