찾기 와 정렬 의 기본 동작: 정렬 알고리즘 집합 찾기
찾기 알고리즘 은 순서 찾기, 2 분 찾기, 해시 표 찾기, 2 차 정렬 트 리 찾기 에 중심 을 두 고 있 습 니 다.
정렬 알고리즘 은 거품 정렬, 삽입 정렬, 병합 정렬, 빠 른 정렬 에 중심 을 두 고 파악 합 니 다.
순서 찾기
알고리즘 설명
저장 구조 가 순서대로 저장 되 거나 링크 로 저장 되 는 선형 표를 순서대로 찾 습 니 다.
알고리즘 사상
순서 찾기 는 선형 찾기 라 고도 부 르 며 무질서 찾기 알고리즘 에 속 합 니 다.데이터 구조 선형 표 의 한 끝 에서 부터 순서대로 스 캔 하고 스 캔 한 노드 키 워드 를 주어진 값 k 와 비교 하 며 같 으 면 검색 성공 을 나타 낸다.검색 이 끝 났 는데 도 키워드 가 k 와 같은 결점 을 찾 지 못 하면 검색 에 실 패 했 음 을 나 타 냅 니 다.
알고리즘 구현
int sequenceSearch(int a[], int value, int len)
{
int i;
for(i=0; i)
if(a[i]==value)
return i;
return -1;
}
알고리즘 분석
검색 에 성공 할 때의 평균 검색 길 이 는: (모든 데이터 요소 의 확률 이 같다 고 가정) ASL = 1 / n (1 + 2 + 3 +... + n) = (n + 1) / 2;검색 에 성공 하지 못 했 을 때 n + 1 번 비교 해 야 합 니 다. 시간 복잡 도 는 O (n) 입 니 다.그래서 순서대로 찾 는 시간의 복잡 도 는 O (n) 이다.
이분 찾기
알고리즘 설명
요 소 는 질서 가 있어 야 합 니 다. 순서 가 없 으 면 정렬 작업 을 먼저 해 야 합 니 다.
알고리즘 사상
반절 검색 이 라 고도 부 르 며 질서 있 는 검색 알고리즘 에 속 합 니 다.주어진 값 k 로 중간 노드 의 키워드 와 비교 하고 중간 노드 는 선형 표를 두 개의 서브 시트 로 나 누 어 같 으 면 찾 는 데 성공 합 니 다.같 지 않 으 면 k 와 이 중간 노드 키워드 의 비교 결과 에 따라 다음 단계 에 어떤 하위 표를 찾 는 지 확인 하고 재 귀적 으로 진행 합 니 다. 찾 거나 찾기 가 끝 날 때 까지 표 에 이러한 결점 이 없습니다.주: 반 으로 나 누 어 찾 는 전제 조건 은 질서 있 는 표 순서 로 저장 해 야 하 는 것 입 니 다. 정적 검색 표 에 대해 한 번 정렬 한 후에 변 하지 않 고 반 으로 나 누 어 찾 으 면 좋 은 효율 을 얻 을 수 있 습 니 다.그러나 삽입 이나 삭제 작업 을 자주 수행 해 야 하 는 데이터 세트 에 있어 서 질서 있 는 정렬 을 유지 하 는 것 은 적지 않 은 작업량 을 가 져 올 수 있 으 므 로 사용 하 는 것 을 권장 하지 않 습 니 다.
알고리즘 구현
// ,
int binarySearch1(int a[], int value, int len)
{
int low, high, mid;
low = 0;
high = len-1;
while(low<=high)
{
mid = low+(high-low)/2; //
if(a[mid]==value)
return mid;
if(a[mid]>value)
high = mid-1;
if(a[mid]<value)
low = mid+1;
}
return -1;
}
// ,
int binarySearch2(int a[], int value, int low, int high)
{
int mid = low+(high-low)/2;
if(a[mid]==value)
return mid;
if(a[mid]>value)
return BinarySearch2(a, value, low, mid-1);
if(a[mid]<value)
return BinarySearch2(a, value, mid+1, high);
}
알고리즘 분석
최 악의 경우 키워드 비교 횟수 는 log 2 (n + 1) 이 므 로 시간 복잡 도 는 O (log2n) 이다.
거품 정렬
알고리즘 설명
교환 클래스 정렬 에 속 하여 안정 적 인 정렬
알고리즘 사상
인접 한 두 수의 크기 를 비교 하고 가장 큰 수 를 오른쪽 에 놓 으 며 계수기 i + +;
a [n - 2] 와 a [n - 1] 가 끝 날 때 까지 1 을 반복 합 니 다. 배열 a 에서 가장 큰 값 은 a [n - 1] 입 니 다.
정렬 을 진행 하 는 배열 의 길이 n 을 1 로 줄 이 고 1 과 2 를 반복 하 며 n 이 1 일 때 까지 정렬 이 완료 되 었 습 니 다.
알고리즘 구현
void bubbleSort(int* array, int length)
{
for (int i = 0; i < length - 1; ++i)
{
//bool is_Swap=false;
for (int j = 0; j < length - 1 - i; ++j)
{
if (array[j] > array[j + 1])
{
//is_Swap=true;
int temp = array[j];
array[j] = array[j + 1];
array[j + 1] = temp;
/*
a = a + b;
b = a - b;
a = a - b;
a=a^b;
b=b^a;
a=a^b;
*/
}
}
//if(is_Swap==false)
//return;
}
}
알고리즘 분석
평균 시간 복잡 도: O (n ^ 2).가장 좋 은 상황: 정렬 을 기다 리 는 데이터 서열 이 정상 이면 거품 이 한 번 에 발생 하면 정렬 을 완성 할 수 있 습 니 다. 정렬 의 비교 횟수 는 n - 1 회 이 고 이동 하지 않 으 며 시간 복잡 도 는 O (n) 입 니 다.O (n) 의 복잡 도 를 실현 하려 면 코드 에 플래그 비트 (Bool 변수) 를 추가 해 야 합 니 다.최 악의 경우: 정렬 을 기다 리 는 데이터 서열 이 역순 이면 거품 정렬 은 n - 1 번 이 필요 하 다. 매번 n - i 번 정렬 의 비교 와 이동, 즉 비교 와 이동 횟수 가 모두 최대 치 에 달한다. 비교 횟수 = n (n - 1) / 2 = O (n ^ 2), 이동 횟수 는 비교 횟수 와 같 기 때문에 최 악의 시간 복잡 도 는 O (n ^ 2) 이다.
삽입 정렬
알고리즘 설명
삽입 클래스 정렬 에 속 하고 정렬 이 안정 적 입 니 다.
알고리즘 사상
정렬 할 배열 의 두 번 째 요 소 를 시작 으로 앞의 수 와 크기 를 비교 하여 적당 한 위 치 를 찾 아 모든 요소 가 삽 입 될 때 까지 삽입 합 니 다.
알고리즘 구현
void insertSort(int* array,int length)
{
int i = 0, j = 0, temp = 0;
for (i = 1; i < length; ++i)
{
// , ,
// 。
if (array[i] < array[i-1])
{
temp = array[i];
for (j = i-1; temp < array[j] && j >= 0 ; --j)
{
array[j+1] = array[j];
}
array[j + 1] = temp;
}
}
}
알고리즘 분석
평균 시간 복잡 도: O (n ^ 2).가장 좋 은 상황: 정렬 대기 기록 이 질서 가 있 을 때 비교 해 야 할 횟수 는 n - 1 = O (n) 입 니 다.최 악의 경우: 정렬 대기 기록 이 역순 이면 가장 많은 비교 횟수 는 n * (n - 1) / 2 = O (n ^ 2) 입 니 다.
정렬
알고리즘 설명
응용 이 넓 고 정렬 이 안정 적 입 니 다.
알고리즘 사상
병합 정렬 은 분 치 법의 전형 적 인 응용 으로 먼저 모든 하위 서열 을 질서 있 게 한 다음 에 모든 하위 서열 을 질서 있 게 한다.두 개의 질서 있 는 하위 서열 을 하나의 질서 있 는 표 로 합 쳐 2 번 병합 이 라 고 한다. 단계: 우선 질서 있 는 수열 을 1 분 2, 2 분 4 로 나 누 어....................................................................그리고 합병 을 진행 합 니 다. 매번 합병 은 질서 있 게 합 쳐 집 니 다.
알고리즘 구현
void MergeArray(int* array, int first, int mid, int last, int* temp)
{
// a[first...mid] a[mid+1...last]
int i = first, j = mid + 1, k = 0;
int lengthA = mid+1, lengthB = last+1;
while (i < lengthA&&j < lengthB)
{
if (array[i] < array[j])
temp[k++] = array[i++];
else
temp[k++] = array[j++];
}
while (i < lengthA)
{
temp[k++] = array[i++];
}
while (j < lengthB)
{
temp[k++] = array[j++];
}
for (i = 0; i < k; ++i)
{
array[first + i] = temp[i];
}
}
void MergeSort(int* array, int first, int last, int* temp)
{
if (first >= last)
return;
int mid = (first + last) / 2;
MergeSort(array, first, mid, temp);//
MergeSort(array, mid + 1, last, temp);//
MergeArray(array, first, mid, last, temp);//
}
알고리즘 분석
평균, 최고, 최 악의 시간 복잡 도: O (n * log n)
이렇게 이해 할 수 있 습 니 다. 합병 은 O (log n) 단계 작업 이 필요 합 니 다. 모든 단계 에서 정렬 된 하위 서열 을 합병 하려 면 O (n) 의 작업 이 필요 합 니 다.그 시간 복잡 도 는 틀림없이 O (n * log n) 일 것 이다.
빠 른 정렬
알고리즘 설명
교환 류 정렬 알고리즘 중에서 빠 른 배열 이 가장 빠르다.분 치 된 사상 을 채택 하여 불안정 하 게 순 위 를 매 긴 다.
알고리즘 사상
n 개의 요소 중에서 하나의 요 소 를 구역 의 기준 으로 선택 하고 보통 첫 번 째 요 소 를 선택한다.
이 원소 보다 작은 것 을 왼쪽 에 놓 고 이 원소 보다 큰 것 을 오른쪽 에 놓 으 면 중간 에 이 원 소 를 놓는다.
다시 좌우 서열 에 대해 1 과 2 를 반복 해서 각 서열 에 하나의 요소 만 있 고 정렬 이 끝 날 때 까지 한다.
알고리즘 구현
// 1
void QuickSort(int* array,int low,int high)
{
if (low >= high)
return;
int left = low;
int right = high;
int key = array[left];// , 。
while (left != right)
{
while (left != right&&array[right] >= key)// , key key
--right;
array[left] = array[right];
while (left != right&&array[left] <= key)// , key key
++left;
array[right] = array[left];
}
array[left] = key;// left right
// , , 。
QuickSort(array, low, left - 1);
QuickSort(array, left + 1, high);
}
알다 시 피 Partition 함 수 는 빠 른 정렬 에서 든 K 대 를 찾 는 문제 에서 든 모두 중요 한 위 치 를 차지 하기 때문에 따로 쓰 면 버 전 2 가 있다.
int Partition(int* array,int left,int right)
{
int key = array[left];
while (left != right)
{
while (left != right&&array[right] >= key)// , key key
--right;
array[left] = array[right];
while (left != right&&array[left] <= key)// , key key
++left;
array[right] = array[left];
}
array[left] = key;
return left;//
}
//
void quicksort(int* arr, int left, int right)
{
if(left< right)
{
int middle = mypartition(arr, left, right);
quicksort(arr, left, middle-1);
quicksort(arr, middle+1, right);
}
}
알고리즘 분석
평균 시간 복잡 도: O (n * log n).원인: 빠 른 배열 은 배열 을 끝까지 나 누 는 것 이기 때문에 O (log n) 번 이 작업 이 필요 합 니 다. 매번 작업 할 때 n 번 을 정렬 해 야 하기 때문에 대부분의 경우 시간 복잡 도 는 O (n * log n) 입 니 다.가장 좋 은 상황: 매번 정렬 이 끝 난 후에 매번 에 두 개의 키 파일 의 길 이 를 대체적으로 같 게 하고 시간 복잡 도 는 O (n * log n) 이다.최 악의 경우: 정렬 대기 요소 가 정렬 되 어 있 습 니 다.n - 1 차 비 교 를 거 친 후 첫 번 째 요 소 는 위치 가 변 하지 않 고 n - 1 개 요소 의 하위 서열 을 얻 을 수 있 습 니 다.두 번 째 는 n - 2 차 비 교 를 통 해 두 번 째 요 소 를 원래 의 위치 에 위치 시 키 고 n - 2 개 요 소 를 포함 한 하위 서열 을 얻어 순서대로 유추 합 니 다. 이렇게 총 비교 횟수 는 n (n - 1) / 2 = O (n ^ 2) 입 니 다.
다음으로 전송:https://www.cnblogs.com/parzulpan/p/11258491.html
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.