算法分析与初学了解 .ppt

An Example: Insertion Sort InsertionSort(A, n) {for i = 2 to n { key = A[i] j = i - 1; while (j 0) and (A[j] key) { A[j+1] = A[j] j = j - 1 }  A[j+1] = key} } 10 30 40 20 1 2 3 4 i = 4 j = 3 key = 20A[j] = 40 A[j+1] = 20 An Example: Insertion Sort InsertionSort(A, n) {for i = 2 to n { key = A[i] j = i - 1; while (j 0) and (A[j] key) { A[j+1] = A[j] j = j - 1 }  A[j+1] = key} } 10 30 40 20 1 2 3 4 i = 4 j = 3 key = 20A[j] = 40 A[j+1] = 20 An Example: Insertion Sort InsertionSort(A, n) {for i = 2 to n { key = A[i] j = i - 1; while (j 0) and (A[j] key) { A[j+1] = A[j] j = j - 1 }  A[j+1] = key} } 10 30 40 40 1 2 3 4 i = 4 j = 3 key = 20A[j] = 40 A[j+1] = 40 An Example: Insertion Sort InsertionSort(A, n) {for i = 2 to n { key = A[i] j = i - 1; while (j 0) and (A[j] key) { A[j+1] = A[j] j = j - 1 }  A[j+1] = key} } 10 30 40 40 1 2 3 4 i = 4 j = 3 key = 20A[j] = 40 A[j+1] = 40 An Example: Insertion Sort InsertionSort(A, n) {for i = 2 to n { key = A[i] j = i - 1; while (j 0) and (A[j] key) { A[j+1] = A[j] j = j - 1 }  A[j+1] = key} } 10 30 40 40 1 2 3 4 i = 4 j = 3 key = 20A[j] = 40 A[j+1] = 40 An Example: Insertion Sort InsertionSort(A, n) {for i = 2 to n { key = A[i] j = i - 1; while (j 0) and (A[j] key) { A[j+1] = A[j] j = j - 1 }  A[j+1] = key} } 10 30 40 40 1 2 3 4 i = 4 j = 2 key = 20A[j] = 30 A[j+1] = 40 An Example: Insertion Sort InsertionSort(A, n) {for i = 2 to n { key = A[i] j = i - 1; while (j 0) and (A[j] key) { A[j+1] = A[j] j = j - 1 }  A[j+1] = key} } 10 30 40 40 1 2 3 4 i = 4 j = 2 key = 20A[j] = 30 A[j+1] = 40 An Example: Insertion Sort InsertionSort(A, n) {for i = 2 to n { key = A[i] j = i - 1; while (j 0) and (A[j] key) { A[j+1] = A[j] j = j - 1 }  A[j+1] = key} } 10 30 30 40 1 2 3 4 i = 4 j = 2 key = 20A[j] = 30 A[j+1] = 30 An Example: Insertion Sort InsertionSort(A, n) {for i = 2 to n { key = A[i] j = i - 1; while